結果
問題 | No.1112 冥界の音楽 |
ユーザー |
|
提出日時 | 2020-07-10 23:19:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 1,507 bytes |
コンパイル時間 | 1,790 ms |
コンパイル使用メモリ | 177,436 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-11 18:37:07 |
合計ジャッジ時間 | 2,993 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; constexpr int INF = 1e9; constexpr long long LINF = 1e17; constexpr int MOD = 1000000007; constexpr double PI = 3.14159265358979323846; using vec = vector<ll> ; using mat = vector<vec>; mat mul(mat &A, mat &B,int mod) { 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 poww(mat A,ll n,int mod){ mat B(A.size(), vec(A.size())); for(int i=0;i<A.size();i++) B[i][i] = 1; while(n > 0){ if(n & 1) B = mul(B,A,mod); A = mul(A,A,mod); n >>= 1; } return B; } int main(){ int k,m; cin >> k >> m; ll n; cin >> n; vector<int> p(m),q(m),r(m); rep(i,m) cin >> p[i] >> q[i] >> r[i]; rep(i,m) --p[i],--q[i],--r[i]; auto id = [&](int a,int b){return a+b*k;}; int t = k*k; mat A(t,vector<ll>(t,0)); rep(i,m){ A[id(p[i],q[i])][id(q[i],r[i])] = 1; } A = poww(A,n-2,MOD); ll ans = 0; rep(i,k)rep(j,k){ ans = (ans + A[id(0,i)][id(j,0)])%MOD; } cout << ans << endl; return 0; }