結果
問題 | No.1112 冥界の音楽 |
ユーザー |
![]() |
提出日時 | 2020-08-12 06:49:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,843 bytes |
コンパイル時間 | 1,533 ms |
コンパイル使用メモリ | 124,696 KB |
最終ジャッジ日時 | 2025-01-12 21:08:02 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
コンパイルメッセージ
main.cpp: In function ‘int main(int, const char**)’: main.cpp:60:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 60 | scanf("%lld %lld %lld", &d[i][0],&d[i][1],&d[i][2]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <iostream> #include <string> #include <vector> #include <queue> #include <deque> #include <algorithm> #include <set> #include <map> #include <bitset> #include <cmath> #include <functional> #include <iomanip> #define vll vector<ll> #define vvvl vector<vvl> #define vvl vector<vector<ll>> #define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c)) #define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c<b;c++) #define all(obj) (obj).begin(), (obj).end() typedef long long int ll; typedef long double ld; using namespace std; #define P 1000000007 vvl dot(vvl A, vvl B){ vvl C = VV(A.size(), B[0].size(), 0, ll); for(int i=0;i<A.size();i++){ for(int j=0;j<B[0].size();j++){ for(int k=0;k<B.size();k++) { C[i][j] = (C[i][j] + (A[i][k]*B[k][j])%P)%P; } } } return C; } vvl mat_pow(vvl A, ll t){ if(t==0){ vvl E = VV(A.size(), A.size(), 0, ll); re(i, A.size()) E[i][i] = 1; return E; } bool flag = true; vvl s; bitset<64> b(t); for(ll i=0;i<64;i++){ if(b[i]) { if(flag) flag = false, s = A; else s = dot(A, s); } A = dot(A, A); } return s; } int main(int argc, char const *argv[]) { ll k, m, n;std::cin >> k >> m >> n; vvl a = VV(k*k, k*k, 0, ll); vvl d = VV(m, 3, 0, ll); re(i, m) { scanf("%lld %lld %lld", &d[i][0],&d[i][1],&d[i][2]); d[i][0]--, d[i][1]--, d[i][2]--; } for(int i=0;i<k;i++){ for(int j=0;j<k;j++){ for(int l=0;l<k;l++){ for(int x=0;x<m;x++){ if(d[x][0]==i&&d[x][1]==j&&d[x][2]==l){ a[i*k+j][j*k+l] = 1; } } } } } vvl b = mat_pow(a, n-2); ll ans = 0; for(int i=0;i<k;i++){//0, i -> j, 1 for(int j=0;j<k;j++){ ans = (ans + b[i][j*k])%P; } } std::cout << ans << '\n'; return 0; }