結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
|
提出日時 | 2021-11-19 22:09:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 258 ms / 2,000 ms |
コード長 | 1,965 bytes |
コンパイル時間 | 2,216 ms |
コンパイル使用メモリ | 200,668 KB |
最終ジャッジ日時 | 2025-01-25 20:24:58 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;// #include <atcoder/all>// using namespace atcoder;#define rep(i, l, r) for (auto i = (l); i < (r); i++)#define all(a) a.begin(), a.end()#define chmin(dest, src) if ((dest) > (src)) dest = (src)#define chmax(dest, src) if ((dest) < (src)) dest = (src)using ll = long long;using i64 = long long;using i32 = long;using u64 = unsigned long long;using u32 = unsigned long;const ll MOD = 998244353;using Type = ll;using Matrix = vector<vector<ll>>;Matrix Mul(const Matrix &a, const Matrix &b) {assert(a[0].size() == b.size());Matrix c(a.size(), vector<Type> (b[0].size(), 0));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) % MOD;}}}return c;}Matrix Pow(Matrix a, long long n) {assert(a.size() == a[0].size());Matrix b(a.size(), vector<Type> (a.size()));for (int i = 0; i < a.size(); i ++) {b[i][i] = 1;}while (n > 0) {if (n & 1) b = Mul(b, a);a = Mul(a, a);n >>= 1;}return b;}void PrintMatrix(const Matrix &a) {int h = a.size(), w = a[0].size();for (int i = 0; i < h; i ++) {for (int j = 0; j < w; j ++) {cout << a[i][j] << ' ';}cout << endl;}}int main() {ll N, M, T;cin >> N >> M >> T;vector<vector<ll>> mat(N, vector<ll>(N, 0));rep (i, 0, M) {int s, t;cin >> s >> t;mat[s][t] = mat[t][s] = 1;}mat = Pow(move(mat), T);ll ans = mat[0][0] % MOD;if (ans < 0) ans += MOD;cout << ans;return 0;}