結果
問題 | No.1112 冥界の音楽 |
ユーザー |
|
提出日時 | 2020-07-10 22:19:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 1,688 bytes |
コンパイル時間 | 382 ms |
コンパイル使用メモリ | 33,664 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-11 09:35:29 |
合計ジャッジ時間 | 1,499 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<cstdio> const long long mod = 1e9+7; long long a[50][50], res[50][50], c[50][50]; long long org[50], ans[50]; void mul(long long u[50][50],long long v[50][50],int n){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ c[i][j] = 0; for(int k = 1; k <= n; k++){ c[i][j] += u[i][k]*v[k][j]%mod; if(c[i][j]>=mod) c[i][j] -= mod; } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) u[i][j] = c[i][j]; } } void power(long long u[50][50],long long b,int n){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) res[i][j] = i==j; } while(b){ if(b&1) mul(res,u,n); mul(u,u,n); b /= 2; } } int main(){ int k,m; long long n; scanf("%d%d%lld",&k,&m,&n); for(int i = 0; i < m; i++){ int p,q,r; scanf("%d%d%d",&p,&q,&r); int from = p*k+q, to = q*k+r; a[to][from] = 1; if(p==1){ //printf("to = %d\n",to); org[to] = 1; } } n -= 3; int total = (k+1)*k; power(a,n,total); /*for(int i = 1; i <= total; i++){ for(int j = 1; j <= total; j++) printf("%lld ",res[i][j]); printf("\n"); }*/ for(int i = 1; i <= total; i++){ long long cur = 0; for(int j = 1; j <= total; j++){ cur += org[j]*res[i][j]%mod; if(cur>=mod) cur -= mod; } ans[i] = cur; } long long sum = 0; for(int i = 1; i <= k; i++){ int id = i*k+1; sum += ans[id]; if(sum>=mod) sum -= mod; } printf("%lld\n",sum); return 0; }