問題
$N$頂点の有向グラフが隣接行列$B$（$B_{i,j}\in\{0,1\}$、多重辺・自己ループなし）として与えられる。整数$K$が与えられる。頂点$s$から辺をちょうど$K$本たどって$s$自身に戻ってくるウォークの総数を、全頂点$s$について合計した値を$\bmod\ M$（$M$は素数）で求めよ。
入力形式
N K M
B_11 B_12 ... B_1N
...
B_N1 B_N2 ... B_NN制約
$1 \le N \le 70$
$1 \le K \le 10^{18}$
$10^8 \le M \le 10^9+9$（素数）
$B_{i,i}=0$
入出力例
入力例1
3 2 1000000007
0 1 0
0 0 1
1 0 0出力例1
03頂点の有向サイクル。サイクル長3は2と互いに素なので長さ2で元頂点に戻る道はない。
入力例2
2 2 1000000007
0 1
1 0出力例2
2B²=単位行列。1→2→1、2→1→2の2通り。
概念図
ヒント（段階的開示）
ヒント1（方向性）
隣接行列$B$の$k$乗の$(i,j)$成分は「頂点$i$から$j$へちょうど$k$本の辺で到達するウォークの本数」に等しい（行列積の定義と経路の合成が対応する）。
ヒント2（アプローチ）
求める値は $\operatorname{tr}(B^K)=\sum_i (B^K)_{i,i}$（トレース）。$K$が最大$10^{18}$なので繰り返し二乗法で$B^K$を$O(\log K)$回の行列積で求める。1回の行列積は$O(N^3)$なので全体$O(N^3\log K)$。
ヒント3（誘導）
def mat_pow(B, k, mod):
n = len(B)
result = [[1 if i==j else 0 for j in range(n)] for i in range(n)] # 単位行列
base = B
while k > 0:
if k & 1:
result = mat_mul(result, base, mod)
base = mat_mul(base, base, mod)
k >>= 1
return result模範解答 (Python)
import sys
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
n = int(data[idx]); idx += 1
k = int(data[idx]); idx += 1
mod = int(data[idx]); idx += 1
b = []
for i in range(n):
row = [int(data[idx + j]) for j in range(n)]
idx += n
b.append(row)
def mat_mul(x, y):
z = [[0] * n for _ in range(n)]
for i in range(n):
xi = x[i]
zi = z[i]
for kk in range(n):
xik = xi[kk]
if xik == 0:
continue
yk = y[kk]
for j in range(n):
zi[j] = (zi[j] + xik * yk[j]) % mod
return z
def mat_pow(mat, p):
result = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
base = mat
while p > 0:
if p & 1:
result = mat_mul(result, base)
base = mat_mul(base, base)
p >>= 1
return result
bk = mat_pow(b, k)
trace = 0
for i in range(n):
trace = (trace + bk[i][i]) % mod
print(trace)
solve()Step-by-Step 解説
1行列積と経路数え上げの対応
$(B^k)_{i,j}=\sum B_{i,c_1}B_{c_1,c_2}\cdots B_{c_{k-1},j}$の各項は長さ$k$のウォークの存在に対応し、総和はその本数になる。
$(B^k)_{i,j}=\sum B_{i,c_1}B_{c_1,c_2}\cdots B_{c_{k-1},j}$の各項は長さ$k$のウォークの存在に対応し、総和はその本数になる。
2トレースの意味
対角成分の総和が「全頂点を始点とする長さKの閉路的ウォークの総数」に一致する。
対角成分の総和が「全頂点を始点とする長さKの閉路的ウォークの総数」に一致する。
3繰り返し二乗法
$K$を2進展開し、$B,B^2,B^4,\dots$を自乗しながらビットが立つ位置だけ結果に掛け合わせる。
$K$を2進展開し、$B,B^2,B^4,\dots$を自乗しながらビットが立つ位置だけ結果に掛け合わせる。
4計算量
1回の行列積$O(N^3)$、$\log K$回程度なので全体$O(N^3\log K)$。
1回の行列積$O(N^3)$、$\log K$回程度なので全体$O(N^3\log K)$。
5mod演算の徹底
行列積の内側ループで毎回modを取ることで数値の爆発的増大を防ぐ。
行列積の内側ループで毎回modを取ることで数値の爆発的増大を防ぐ。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 単位行列の初期化を忘れる | $B^0=I$を用意していない | resultを単位行列で初期化してから二乗法を回す |
| 行列積でmodを取り忘れる | 大きい整数のまま演算し続ける | 各要素更新のたびに%modを適用する |
| トレースを対角成分の最大値と勘違い | 用語の理解不足 | トレースは対角成分の総和 |
| 二分累乗のループ条件を誤る | p=0での終了確認不足 | while p > 0:で正しく終了することを確認 |
次のステップ
- 発展: 長さK以下の閉路的ウォーク総数を求める（等比行列和のブロック行列トリック）
- 次回予告（Master Levelローテーション継続）: 次回セッションで新たな高度テーマを選定