No.044 B

$A_1 \neq 0$ または $A_i = 0$ ($2 \leq i \leq N$) のときはグラフは存在しない.

$A_i = k$ となる $i$ の個数を $b_k$ とする.

頂点 1 と頂点 $i$ の最短距離を $k$ にするためには, $A_i = k-1$ となる頂点にひとつ以上辺をつなぐ必要がある. この組み合わせの数は, $2^{ b_{k-1} } - 1$ である.

また, $A_i = k$ となる頂点同士は辺をつないでもつながなくてもいい. この組み合わせの数は $2^{ {}_{b_k}C_2 }$ である.

よって, すべての組み合わせの数は,

$$\prod_k (2^{ b_{k-1} } - 1)^{b_k} \cdot 2^{ {}_{b_k}C_2 }$$

となる.

${}_nC_r$ は大きくなる可能性があるので, 階乗は繰り返し二乗法を使う.