結果
問題 |
No.1112 冥界の音楽
|
ユーザー |
|
提出日時 | 2021-12-18 20:06:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 1,012 bytes |
コンパイル時間 | 2,826 ms |
コンパイル使用メモリ | 250,788 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 13:53:50 |
合計ジャッジ時間 | 3,895 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h> #define mod 1000000007 using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int k,m; long long n; cin >> k >> m >> n; n-=3; vector<vector<long long>> g(k*k,vector<long long>(k*k,0)); vector<long long> v(k*k,0); for(int i=0;i<m;i++){ int p,q,r; cin >> p >> q >> r; p--;q--;r--; if(p==0){v[q*k+r]++;} g[p*k+q][q*k+r]++; } for(int i=0;i<60;i++){ if(n&(1ll<<i)){ vector<long long> nv(k*k,0); for(int p=0;p<k*k;p++){ for(int q=0;q<k*k;q++){ nv[q]+=v[p]*g[p][q]; nv[q]%=mod; } } v.swap(nv); } vector<vector<long long>> ng(k*k,vector<long long>(k*k,0)); for(int p=0;p<k*k;p++){ for(int q=0;q<k*k;q++){ for(int r=0;r<k*k;r++){ ng[p][r]+=g[p][q]*g[q][r]; ng[p][r]%=mod; } } } g.swap(ng); } long long res=0; for(int i=0;i<k;i++){res+=v[k*i];res%=mod;} cout << res << '\n'; return 0; }