結果
問題 |
No.1112 冥界の音楽
|
ユーザー |
|
提出日時 | 2020-07-10 21:39:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 784 bytes |
コンパイル時間 | 522 ms |
コンパイル使用メモリ | 68,552 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-11 08:24:30 |
合計ジャッジ時間 | 1,586 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
コンパイルメッセージ
main.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 7 | main() | ^~~~
ソースコード
#include<iostream> using namespace std; const long mod=1e9+7; long E[36][36],A[36][36],T[36][36]; int K,M; long N; main() { cin>>K>>M>>N; for(int i=0;i<K*K;i++)E[i][i]=1; for(int i=0;i<M;i++) { int a,b,c;cin>>a>>b>>c; a--,b--,c--; A[b*K+c][a*K+b]++; } N-=2; while(N) { if(N&1) { for(int i=0;i<K*K;i++)for(int j=0;j<K*K;j++)T[i][j]=E[i][j],E[i][j]=0; for(int i=0;i<K*K;i++)for(int j=0;j<K*K;j++) { for(int k=0;k<K*K;k++)(E[i][j]+=A[i][k]*T[k][j])%=mod; } } N>>=1; for(int i=0;i<K*K;i++)for(int j=0;j<K*K;j++)T[i][j]=A[i][j],A[i][j]=0; for(int i=0;i<K*K;i++)for(int j=0;j<K*K;j++) { for(int k=0;k<K*K;k++)(A[i][j]+=T[i][k]*T[k][j])%=mod; } } long ans=0; for(int i=0;i<K;i++)for(int j=0;j<K;j++)ans+=E[j*K][i]; cout<<ans%mod<<endl; }