結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
![]() |
提出日時 | 2021-11-27 14:19:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,057 ms / 2,000 ms |
コード長 | 1,233 bytes |
コンパイル時間 | 1,675 ms |
コンパイル使用メモリ | 173,972 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 04:35:01 |
合計ジャッジ時間 | 13,118 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef vector<vector<int64_t>> Matrix; // 行列の乗算(mod) Matrix ModMultiMatrix(const Matrix &a, const Matrix &b, int64_t mod) { Matrix c(a.size(), vector<int64_t>(b.at(0).size())); for(int i = 0; i < a.size(); i++) { for(int k = 0; k < b.size(); k++) { for(int j = 0; j < b.at(0).size(); j++) { c.at(i).at(j) += a.at(i).at(k) * b.at(k).at(j); c.at(i).at(j) %= mod; } } } return c; } // 行列の累乗(mod) Matrix ModPowerMatrix(Matrix a, int64_t n, int64_t mod) { Matrix b(a.size(), vector<int64_t>(a.size())); for(int i = 0; i < a.size(); i++) b.at(i).at(i) = 1; while(n > 0) { if(n & 1) b = ModMultiMatrix(b, a, mod); a = ModMultiMatrix(a, a, mod); n >>= 1; } return b; } int main() { int64_t N, M, T; cin >> N >> M >> T; int64_t mod = 998244353; Matrix P(N, vector<int64_t>(N)); int64_t s, t; for(int64_t i = 0; i < M; i++) { cin >> s >> t; P.at(s).at(t) = 1; P.at(t).at(s) = 1; } P = ModPowerMatrix(P, T, mod); Matrix F(N, vector<int64_t>(1)); F.at(0).at(0) = 1; Matrix ans = ModMultiMatrix(P, F, mod); cout << ans.at(0).at(0) << endl; return 0; }