結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
![]() |
提出日時 | 2023-07-21 19:33:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,986 ms / 2,000 ms |
コード長 | 1,270 bytes |
コンパイル時間 | 4,666 ms |
コンパイル使用メモリ | 255,148 KB |
最終ジャッジ日時 | 2025-02-15 16:11:56 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> #include<atcoder/all> using namespace atcoder; using namespace std; using ll=long long; using ld=long double; ld pie=3.141592653589793; ll inf=922775807; ll mod=998244353; vector<vector<ll>>mul(vector<vector<ll>>&a,vector<vector<ll>>&b){ vector<vector<ll>>c(a.size(),vector<ll>(b[0].size(),0)); for (ll i = 0; i < a.size(); i++) { for (ll j = 0; j < b[0].size(); j++) { for (ll k = 0; k < a[0].size(); k++) { c[i][j]+=(a[i][k]*b[k][j])%mod; c[i][j]%=mod; } } } return c; } vector<vector<ll>>matpow(vector<vector<ll>>a,ll n){ vector<vector<ll>>b(a.size(),vector<ll>(a.size(),0)); for (ll i = 0; i < a.size(); i++) { b[i][i]=1; } while (n>0) { if (n%2) { b=mul(a,b); n-=1; }else{ a=mul(a,a); n/=2; } } return b; } int main(){ ll n,m,t; cin >> n >> m >> t; vector<vector<ll>>g(n,vector<ll>(n,0)); for (ll i = 0; i < m; i++) { ll s,tt; cin >> s >> tt; g[s][tt]=1; g[tt][s]=1; } vector<vector<ll>>gg=matpow(g,t); ll ans=0; cout << gg[0][0] << endl; }