結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
![]() |
提出日時 | 2021-11-20 18:11:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 340 ms / 2,000 ms |
コード長 | 1,651 bytes |
コンパイル時間 | 5,904 ms |
コンパイル使用メモリ | 253,932 KB |
最終ジャッジ日時 | 2025-01-25 22:13:21 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <math.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define rep(i, l, n) for (int i = (l); i < (n); i++) #define max(p, q) ((p) > (q) ? (p) : (q)) #define min(p, q) ((p) < (q) ? (p) : (q)) #define all(x) x.begin(), x.end() #define fi first #define se second #define lb lower_bound; #define ub upper_bound; #define lbi(A, x) (ll)(lb(all(A), x) - A.begin()) #define ubi(A, x) (ll)(ub(all(A), x) - A.begin()) using ll = long long; using P = pair<int, int>; template <class T> using V = vector<T>; template <class T> using VV = V<V<T> >; template <class T> const ll INF = 1000000000000000001; const int inf = 1001001001; const ll mod = 1000000007; const ll MOD = 998244353; inline V<int> dtois(string& s) { V<int> vec = {}; for (auto& e : s) { vec.push_back(e - '0'); } return vec; } VV<ll> matrix_prod(const VV<ll>& A, const VV<ll>& B) { int ac = A.size(); int al = A[0].size(); int bc = B.size(); int bl = B[0].size(); VV<ll> res(ac, V<ll>(bl)); rep(i, 0, ac) { rep(j, 0, bl) { rep(k, 0, al) { res[i][j] += A[i][k] * B[k][j]; res[i][j] %= MOD; } } } return res; } VV<ll> matrix_exp(VV<ll>A, ll n) { int ac = A.size(); VV<ll> res(ac, V<ll>(ac)); rep(i, 0, ac) { res[i][i] = 1; } while (n) { if (n & 1) { res = matrix_prod(A, res); } A = matrix_prod(A, A); n >>= 1; } return res; } int main(void) { ll n, m, t; cin >> n >> m >> t; VV<ll> A(n, V<ll>(n)); rep(i, 0, m) { int a, b; cin >> a >> b; A[a][b] = A[b][a] = 1; } VV<ll> dp(n, V<ll>(1)); dp[0][0] = 1; dp = matrix_prod(matrix_exp(A, t), dp); cout << dp[0][0] << endl; return 0; }