結果
問題 |
No.1112 冥界の音楽
|
ユーザー |
|
提出日時 | 2022-05-15 10:32:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 254 ms / 2,000 ms |
コード長 | 783 bytes |
コンパイル時間 | 230 ms |
コンパイル使用メモリ | 82,328 KB |
実行使用メモリ | 76,764 KB |
最終ジャッジ日時 | 2024-07-26 12:14:45 |
合計ジャッジ時間 | 3,873 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
K,M,N = map(int,input().split()) P = 10 ** 9 + 7 D = K * K edge = [] for _ in range(M): p,q,r = map(int,input().split()) p -= 1 q -= 1 r -= 1 edge.append((p,q,r)) def seki(x,y): l = [[0] * D for _ in range(D)] for i in range(D): for j in range(D): for k in range(D): l[i][j] += x[i][k] * y[k][j] l[i][j] %= P return l R = [[0] * D for _ in range(D)] for p,q,r in edge: nx = q * K + r be = p * K + q R[nx][be] = 1 e = [[0] * D for _ in range(D)] for i in range(D): e[i][i] = 1 N = N - 2 while N: if N & 1: e = seki(e,R) R = seki(R,R) N >>= 1 ans = 0 for i in range(K): be = i for j in range(K): nx = j * K ans += e[nx][be] print(ans % P)