結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
|
提出日時 | 2023-07-15 19:59:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 397 ms / 2,000 ms |
コード長 | 1,380 bytes |
コンパイル時間 | 1,218 ms |
コンパイル使用メモリ | 112,148 KB |
最終ジャッジ日時 | 2025-02-15 15:08:01 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
// #include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<cmath> #include <unordered_set> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<ll,ll> P; typedef pair<int,P> PP; const ll MOD=998244353; vector<vector<ll> > mat(vector<vector<ll> > A,vector<vector<ll> > B,int N){ //A*B vector<vector<ll> > C(N,vector<ll>(N)); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ ll ans=0; for(int k=0;k<N;k++){ ans = (ans + A[i][k]*B[k][j]%MOD)%MOD; } C[i][j] = ans; } } return C; } //行列xのy乗 vector<vector<ll> > multi_matrix(vector<vector<ll> >x, ll y ,int N){ vector<vector<ll> > pow(N,vector<ll>(N)); for(int i=0;i<N;i++) pow[i][i]=1;//単位行列 while(y>0){ if(y&1){ pow = mat(pow,x,N); } y = y>>1; x = mat(x,x,N); } return pow; } int main(){ int N,M; ll T; cin>>N>>M>>T; vector<vector<ll>> matrix(N,vector<ll>(N,0)); for(int i=0;i<M;i++){ int s,t; cin>>s>>t; matrix[s][t]=1; matrix[t][s]=1; } auto res=multi_matrix(matrix,T,N); ll ans=0; ans+=res[0][0]*1; cout<<ans<<endl; }