Submission #41261925

---

Source Code Expand

import sys
def input():
    return sys.stdin.readline().rstrip()
# EDPC R - Walk
N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
# 隣接リスト
G = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if A[i][j]:
            G[i].append(j)
MOD = 10**9+7
# 長さK
# 単純有向グラフ
# ダブリング?
# 計算量は最大で2500*2500*60 3*10**8 間に合わない？
# dp[i][j][k]jから2**i回移動するとkにいる数
H = len(bin(K)[2:])
dp = [[[0]*N for i in range(N)] for _ in range(H)]
#初期化
for j in range(N):
    for v in G[j]:
        dp[0][j][v] += 1
for i in range(H-1):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # jからkに移動
                dp[i+1][j][k] = (dp[i+1][j][k]+dp[i][j][l]*dp[i][l][k])%MOD
#print(dp)
S = bin(K)[2:][::-1]
prev = [1]*N
for i in range(H):
    if S[i] == "0":continue
    cur = [0]*N
    for j in range(N):
        for k in range(N):
            cur[k] += prev[j]*dp[i][j][k]
            cur[k] %= MOD
    prev = cur
print(sum(prev)%MOD)

Submission Info

Judge Result