結果
問題 | No.1112 冥界の音楽 |
ユーザー |
![]() |
提出日時 | 2020-07-10 22:39:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 713 bytes |
コンパイル時間 | 376 ms |
コンパイル使用メモリ | 81,988 KB |
実行使用メモリ | 74,300 KB |
最終ジャッジ日時 | 2024-10-11 10:01:24 |
合計ジャッジ時間 | 3,667 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
K,M,N=map(int,input().split()) A=[[0]*(K*K) for i in range(K*K)] for i in range(0,K*K,K): A[i][-1]=1 P,Q,R=0,0,0 B=[[0]*(K*K) for i in range(K*K)] for i in range(M): P,Q,R=map(int,input().split()) P,Q,R=P-1,Q-1,R-1 B[Q+R*K][P+Q*K]+=1 mod=10**9+7 def m(a,b): r=[[0]*len(b[0]) for i in range(len(a))] for i in range(len(a)): for k in range(len(b)): for j in range(len(b[0])): r[i][j]=(r[i][j]+a[i][k]*b[k][j])%mod return r def p(a,n): r=[[0]*len(a) for i in range(len(a))] b=[] for i in range(len(a)): r[i][i]=1 b.append(a[i][:]) l=n while l>0: if l&1: r=m(b,r) b=m(b,b) l>>=1 return r X=m(p(B,N-2),A) print(sum(map(lambda x:x[-1],X[:K]))%mod)