結果
問題 |
No.1750 ラムドスウイルスの感染拡大-hard
|
ユーザー |
![]() |
提出日時 | 2021-11-26 14:57:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 343 ms / 2,000 ms |
コード長 | 1,971 bytes |
コンパイル時間 | 314 ms |
コンパイル使用メモリ | 51,328 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-29 11:30:50 |
合計ジャッジ時間 | 4,877 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
/* -*- coding: utf-8 -*- * * 1750.cc: No.1750 ラムドスウイルスの感染拡大-hard - yukicoder */ #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; /* constant */ const int MAX_N = 100; const int MOD = 998244353; /* typedef */ typedef long long ll; template<const int MOD> struct MI { int v; MI(): v() {} MI(int _v): v(_v % MOD) {} MI(long long _v): v(_v % MOD) {} MI operator+(const MI m) const { return MI(v + m.v); } MI operator-(const MI m) const { return MI(v + MOD - m.v); } MI operator*(const MI m) const { return MI((long long)v * m.v); } MI &operator+=(const MI m) { return (*this = *this + m); } MI &operator-=(const MI m) { return (*this = *this - m); } MI &operator*=(const MI m) { return (*this = *this * m); } }; typedef MI<MOD> mi; typedef mi vec[MAX_N]; typedef vec mat[MAX_N]; /* global variables */ mat ma, mb; /* subroutines */ inline void initmat(const int n, mat a) { memset(a, 0, sizeof(mat)); } inline void unitmat(const int n, mat a) { initmat(n, a); for (int i = 0; i < n; i++) a[i][i] = 1; } inline void copymat(const int n, const mat a, mat b) { memcpy(b, a, sizeof(mat)); } inline void mulmat(const int n, const mat a, const mat b, mat c) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { c[i][j] = 0; for (int k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } } inline void powmat(const int n, const mat a, ll b, mat c) { mat s, t; copymat(n, a, s); unitmat(n, c); while (b > 0) { if (b & 1) { mulmat(n, c, s, t); copymat(n, t, c); } mulmat(n, s, s, t); copymat(n, t, s); b >>= 1; } } /* main */ int main() { int n, m; ll t; scanf("%d%d%lld", &n, &m, &t); initmat(n, ma); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); ma[u][v] = ma[v][u] = 1; } powmat(n, ma, t, mb); printf("%d\n", mb[0][0].v); return 0; }