結果
問題 | No.1112 冥界の音楽 |
ユーザー |
![]() |
提出日時 | 2020-07-10 23:13:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,637 bytes |
コンパイル時間 | 2,102 ms |
コンパイル使用メモリ | 200,108 KB |
最終ジャッジ日時 | 2025-01-11 19:12:52 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i=0; i<n; i++) #define pb push_back //#define int long long typedef vector<long long> vec; typedef vector<vec> mat; const long long MOD = 1000000007; int K, M; long long N; int serial[10][10]; bool ok[10][10][10]; mat mat_mul(mat A, mat B) { mat C(A.size(), vec(B[0].size())); for (int i=0; i<A.size(); i++) { for (int j=0; j<B[0].size(); j++) { for (int k=0; k<A[0].size(); k++) { C[i][j] += A[i][k]*B[k][j]; C[i][j] %= MOD; } } } return C; } mat mat_pow(mat A, long long n) { mat res(A.size(), vec(A.size())); for (int i=0; i<A.size(); i++) { res[i][i] = 1; } while (n > 0) { if (n & 1) { res = mat_mul(A, res); } n >>= 1; A = mat_mul(A, A); } return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> K >> M; cin >> N; if (N==3) { int ans = 0; rep(i, M) { int P, Q, R; cin >> P >> Q >> R; if (P==1 && R==1) ans++; } cout << ans << endl; exit(0); } int c = 0; rep(i, K) rep(j, K) { serial[i][j] = c; c++; } mat A(c, vec(c)); rep(i, M) { int P, Q, R; cin >> P >> Q >> R; A[serial[P-1][Q-1]][serial[Q-1][R-1]] += 1; } mat res = mat_pow(A, N-2); long long ans = 0; rep(i, K) rep(j, K) { ans += res[serial[0][i]][serial[j][0]]; ans %= MOD; } cout << ans << endl; }