ゆらのふなびと

競プロ, Python, C++

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)

考察ゲーしんどいです.