結果
問題 | No.1112 冥界の音楽 |
ユーザー |
![]() |
提出日時 | 2020-07-10 23:43:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 84 ms / 2,000 ms |
コード長 | 1,375 bytes |
コンパイル時間 | 2,054 ms |
コンパイル使用メモリ | 201,724 KB |
最終ジャッジ日時 | 2025-01-11 19:20:19 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;} template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;} ll dx[4]={0,1,-1,0}; ll dy[4]={1,0,0,-1}; typedef vector<ll> vec; typedef vector<vec> mat; ll mod=1e9+7; mat mul(mat &a,mat&b){ mat c(a.size(),vec(b[0].size())); for (int i = 0; i < a.size(); i++){ for (int k = 0; k < b.size(); k++){ for (int j = 0; j < b[0].size(); j++){ c[i][j]=(c[i][j] + a[i][k] * b[k][j]) %mod; } } } return c; } mat matpow(mat a,ll m){ mat b(a.size(),vec(a.size())); for (int i = 0; i < a.size(); i++){ b[i][i]=1; } while(m>0){ if(m&1) b=mul(b,a); a=mul(a,a); m>>=1; } return b; } mat A(36,vec(36)); // ans = A[1][0] signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); ll k,m,n; cin>>k>>m>>n; for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; c--,a--,b--; A[b*6+c][a*6+b] = 1; } A = matpow(A,n-2); ll ans = 0; for(int i=0;i<k;i++){ for(int j=0;j<k;j++){ ans += A[6*i][j]; ans %= mod; } } cout << ans << endl; }