ARC042 B - 最短路問題 - ゆらのふなびと

いきなり公式の解説を読んでもわからなかったので，具体例による考え方を書いておく．あとはPythonのpowの使い方．

問題

同じ頂点の間を結ぶ辺が複数存在せず、またすべての辺の2端点の頂点が異なるグラフの頂点を順に1,2,…,Nとして、任意のiに対し、頂点1と頂点iを結ぶ経路上に存在する辺の個数の最小値が（編注：“ちょうど”）A_iになるようなグラフの総数を数えます。

整数NとA_1,…,A_Nが与えられるので、このようなグラフの個数を 10**9 + 7 で割った余りを求めてください。

解法

問題文が難しいのだが，自分は編注のところがわかっていなかったようである．ということに今気づいた．

具体例

入力例1を用いて問題を読み解いていこう．一気に考えると難しいので，最短距離 $C$ が小さい方から順に何通りかを考える．便宜上Aは昇順にソートされているものとする．( $A = [0, 1, 1, 2$ ])

$C = 0$ について

これは最初の点(1)であるから，まだ1通り．

次は $C = 1$ であるが，これは以下のように2つに分けて考えるとよい．

$C = 0$ と $C = 1$ のつなぎ方について

最短距離1の点は，点1と直接つながっている点である．よって点2と点1, 点3と点1のつなぎ方は各々1通り．

$C = 1$ どうしのつなぎ方について

点2と点3の間のつなぎ方はどうか．結論から言うとこれは「どんな張り方でもよい」．なぜなら点2と点3の間に辺があっても，点2と点1との最短距離，および点3と点1との最短距離には影響を及ぼさないからだ．よって点2と点3とのつなぎ方は，以下のように求まる．（後の一般化のため，少々冗長な方法を用いる．）

それぞれの辺について，つなぐかつながないかの2通り

辺の数は ${}_2 C_2$ (2つの頂点から，辺の両端となる点を2つ選ぶ)

したがって，点2と点3とのつなぎ方は $2^{ {}_2 C_2 } = 2$ 通り．

$C = 2$ も上と同様に2つに分けて考える．

$C = 1$ と $C = 2$ のつなぎ方について

$C = 2$ の点4は， $C = 1$ の点2, 3のうち少なくとも1つと直接辺が張られていればよい．よって以下のように求まる（これも一般化のため云々．）

$C = 2$ に含まれるある点と， $C = 1$ に含まれる点(2個)とのつなぎ方は $2^{2}$

そのうち，「どの辺も張られていない」が1通り．

よって， $C = 2$ に含まれるある点が， $C = 1$ に含まれる点のうち少なくとも1つと直接辺が張られているような場合の数は $2^{2} - 1$ 通り．

$C = 2$ に含まれる点の数は1個(点4のみ)

したがって， $C = 1$ と $C = 2$ のつなぎ方は $(2^{2} - 1)^{1} = 3$ 通り．

$C = 2$ どうしのつなぎ方について

$C = 2$ の点は1つ(点4)のみしかないので，これは1通り．

まとめ

以上はすべて「かつ」なので，掛け算して，答えは $1 * 1 * 2 * 3 * 1 = 6$ 通りとなる．

一般の場合

↑を読んでから公式の解説を読めば内容がわかると思うので，一般式はそちらに譲る．基本的には↑で出てきた数式をプログラムに書くだけ．

以下のコードのポイントとしては，

計算式で「各Cについて，最短距離Cの点の個数」が必要なので，それを配列bにカウントしている
配列bの操作をする際，止まる場所が分かるようにmaxを記録している
Pythonではpow(x, y, z) で x ** y % z を高速に計算できる
aの中身が不連続な場合，たとえばA = [0, 1, 1, 3]ならC=1とC=3の間に辺が張れないので0通りだが，このコードのようにループすれば計算の過程で「*0」がでてきて答えが0になるので，例外処理しなくてもよい

MOD = 10**9 + 7
 
N = int(input())
a = list(map(int, input().split()))
 
b = [0] * N
mx = 0
for ax in a:
    b[ax] += 1
    mx = max(mx, ax)
 
if a[0] != 0 or b[0] > 1:
    print(0)
    exit()
 
ans = 1
for i in range(1, mx+1):
    ans = ans * pow(2, b[i] * (b[i] - 1) // 2, MOD) % MOD
    ans = ans * pow(pow(2, b[i-1], MOD) - 1, b[i], MOD) % MOD
print(ans)

考察ゲーしんどいです．