結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
|
提出日時 | 2021-11-19 21:51:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 348 ms / 2,000 ms |
コード長 | 5,855 bytes |
コンパイル時間 | 2,502 ms |
コンパイル使用メモリ | 205,756 KB |
最終ジャッジ日時 | 2025-01-25 20:17:40 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<const int MOD> struct modint{long long val;modint(): val(0) {}modint(long long x){if(x < 0) val = x % MOD + MOD;else val = x % MOD;}modint(const modint &t){val = t.val;}modint& operator =(const modint m){val = m.val;return *this;}modint operator -(){return modint(-val);}modint& operator-=(const modint &m){val -= m.val;if(val < 0) val += MOD;return *this;}modint& operator+=(const modint &m){val += m.val;if(val >= MOD) val -= MOD;return *this;}modint& operator*=(const modint &m){val *= m.val;val %= MOD;return *this;}modint& operator/=(modint m){*this *= m.inv();return *this;}modint inv(){long long x = 1, y = 0;long long a = val, b = MOD;while(b != 0){long long t = a / b;a -= t * b;x -= t * y;swap(a, b);swap(x, y);}x %= MOD;if(x < 0) x += MOD;return modint(x);}modint pow(long long k){long long res = 1;long long v = val;while(k > 0){if(k & 1) res = res * v % MOD;v = v * v % MOD;k >>= 1;}return modint(res);}bool operator==(const modint &m){return val == m.val;}modint operator+(const modint &m){return modint(*this) += m;}modint operator-(const modint &m){return modint(*this) -= m;}modint operator*(const modint &m){return modint(*this) *= m;}modint operator/(const modint &m){return modint(*this) /= m;}bool operator!=(const modint &m){return modint(*this).val != m.val;}bool operator!=(const int &m){return modint(*this).val != m;}};const int MOD = 998244353;using mint = modint<MOD>;const int MAX = 410000;mint fac[MAX], finv[MAX], inv[MAX];void COMinit(){fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for(int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i;inv[i] = mint(MOD) - inv[MOD % i] * (MOD / i);finv[i] = finv[i - 1] * inv[i];}}mint COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * finv[k] * finv[n - k];}template<typename T> struct mat{vector<vector<T>> matrix;//行列int N, M;mat(){}mat(int n, int m): N(n), M(m){matrix.resize(n, vector<T>(m));}mat(vector<vector<T>> m) : N(m.size()), M(m[0].size()), matrix(m){}vector<T> operate(vector<T> &vec){//ベクトルにかけるassert(vec.size() == M);vector<T> res(N);for(int i = 0; i < N; i++){for(int j = 0; j < M; j++) res[i] += (*this)[i][j] * vec[j];}return res;}mat I(int N){mat m(N, N);for(int i = 0; i < N; i++) m[i][i] = 1;return (m);}mat& pow(long long K){assert(N == M);//正方行列である必要ありmat temp(I(N));while(K > 0){if(K & 1) temp *= *this;*this *= *this;K >>= 1;}matrix.swap(temp.matrix);return *this;}const vector<T> &operator[](int i) const{return matrix.at(i);}vector<T>& operator[](int i){return matrix.at(i);}mat& operator*=(const mat &mat2){vector<vector<T>> res(N, vector<T>(M));for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){for(int k = 0; k < M; k++){res[i][j] += (*this)[i][k] * mat2[k][j];}}}matrix.swap(res);return *this;}mat& operator^=(const mat &mat2){assert(N == mat2.N && M == mat2.M);for(int i = 0; i < N; i++){for(int j = 0; j < M; j++) (*this)[i][j] ^= mat2[i][j];}return *this;}mat& operator|=(const mat &mat2){assert(N == mat2.N && M == mat2.M);for(int i = 0; i < N; i++){for(int j = 0; j < M; j++) (*this)[i][j] |= mat2[i][j];}return *this;}mat& operator&=(const mat &mat2){assert(N == mat2.N && M == mat2.M);for(int i = 0; i < N; i++){for(int j = 0; j < M; j++) (*this)[i][j] &= mat2[i][j];}return *this;}mat& operator+=(const mat &mat2){assert(N == mat2.N && M == mat2.M);for(int i = 0; i < N; i++){for(int j = 0; j < M; j++) (*this)[i][j] += mat2[i][j];}return *this;}mat& operator-=(const mat &mat2){assert(N == mat2.N && M == mat2.M);for(int i = 0; i < N; i++){for(int j = 0; j < M; j++) (*this)[i][j] -= mat2[i][j];}return *this;}mat operator+(const mat &mat1){return mat(*this) += mat1;}mat operator-(const mat &mat1){return mat(*this) -= mat1;}mat operator*(const mat &mat2){return mat(*this) *= mat2;}mat operator&(const mat &mat1){return mat(*this) &= mat1;}mat operator|(const mat &mat1){return mat(*this) |= mat1;}mat operator^(const mat &mat1){return mat(*this) ^= mat1;}};int main(){int N, M;cin >> N >> M;long long T;cin >> T;mat<mint> V(N, N);for(int i = 0; i < M; i++){int a, b;cin >> a >> b;V[a][b] = 1;V[b][a] = 1;}vector<mint> ans(N);ans[0] = 1;V.pow(T);ans = V.operate(ans);cout << ans[0].val << endl;}