結果
問題 | No.1112 冥界の音楽 |
ユーザー |
|
提出日時 | 2020-07-10 23:15:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 2,785 bytes |
コンパイル時間 | 3,300 ms |
コンパイル使用メモリ | 199,620 KB |
最終ジャッジ日時 | 2025-01-11 19:13:09 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
/*** author: yuji9511 ***/ #include <bits/stdc++.h> using namespace std; using ll = long long; using lpair = pair<ll, ll>; const ll MOD = 1e9+7; const ll INF = 1e18; #define rep(i,m,n) for(ll i=(m);i<(n);i++) #define rrep(i,m,n) for(ll i=(m);i>=(n);i--) #define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];}; void print() {} template <class H,class... T> void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);} ll dp[110][310][310] = {}; typedef vector<ll> vec; typedef vector<vec> mat; mat mult(mat &A, mat &B){ mat C(A.size(), vec(B[0].size(),0)); rep(i,0,A.size()){ rep(k,0,B.size()){ rep(j,0,B[0].size()){ C[i][j] += A[i][k] * B[k][j]; C[i][j] %= MOD; } } } return C; } mat pow_mat(mat A, ll n){ if(n == 1) return A; if(n % 2 == 0){ mat B = pow_mat(A, n/2); return mult(B,B); }else{ mat B = pow_mat(A, n-1); return mult(A,B); } } void solve(){ ll K,M,N; cin >> K >> M >> N; ll P[250], Q[250], R[250]; rep(i,0,M){ cin >> P[i] >> Q[i] >> R[i]; P[i]--; Q[i]--; R[i]--; } mat A(K*K, vec(K*K,0)); if(N == 3){ ll res = 0; rep(i,0,M){ if(P[i] == 0 && R[i] == 0) res++; } print(res); return; } rep(i,0,M){ ll v1 = K * Q[i] + R[i]; ll v2 = K * P[i] + Q[i]; A[v1][v2]++; } // rep(i,0,K*K){ // rep(j,0,K*K){ // cout << A[i][j] << " "; // } // cout << endl; // } mat res = pow_mat(A, N-3); // rep(i,0,K*K){ // rep(j,0,K*K){ // cout << res[i][j] << " "; // } // cout << endl; // } ll arr[50] = {}; rep(i,0,M){ if(P[i] == 0) arr[K * Q[i] + R[i]]++; } ll ans = 0; rep(i,0,K){ ll v = K * i + 0; rep(j,0,K*K){ ans += res[v][j] * arr[j] % MOD; ans %= MOD; } } print(ans); // rep(i,0,M){ // if(N == 3){ // if(P[i] == 0 && R[i] == 0) dp[3][Q[i]][R[i]]++; // }else{ // if(P[i] == 0) dp[3][Q[i]][R[i]]++; // } // } // rep(i,4,N+1){ // if(i == N){ // rep(j,0,M){ // if(R[j] == 0) dp[i][Q[j]][R[j]] += dp[i-1][P[j]][Q[j]]; // } // }else{ // rep(j,0,M){ // dp[i][Q[j]][R[j]] += dp[i-1][P[j]][Q[j]]; // } // } // } // ll ans = 0; // rep(i,0,K){ // rep(j,0,K){ // ans += dp[N][i][j]; // } // } // print(ans); } int main(){ cin.tie(0); ios::sync_with_stdio(false); solve(); }