結果
問題 | No.1749 ラムドスウイルスの感染拡大 |
ユーザー |
|
提出日時 | 2021-11-19 21:39:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 5,036 bytes |
コンパイル時間 | 1,937 ms |
コンパイル使用メモリ | 200,692 KB |
最終ジャッジ日時 | 2025-01-25 20:07:21 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h>typedef uint64_t u64;typedef int64_t i64;using namespace std;void solve();int main(){cout<<fixed<<setprecision(15);bool is_multicase=false;int T=1;if(is_multicase){cin>>T;}for(int i=0;i<T;++i){solve();}return 0;}template<typename T> void turtle_in(T& n){cin>>n;}template<typename T,typename U> void turtle_in(pair<T,U>& p){turtle_in(p.first);turtle_in(p.second);}template<typename T> void turtle_in(vector<T>& v){for(auto& u:v){turtle_in(u);}}template<typename T> void turtle_out(T& n){cout<<n;}template<typename T,typename U> void turtle_out(pair<T,U>& p){cout<<"{";turtle_out(p.first);cout<<", ";turtle_out(p.second);cout<<"}";}template<typename T> void turtle_out(vector<T>& v){for(int i=0;i<int(v.size());++i){turtle_out(v[i]);if(i!=v.size()-1){cout<<" ";}}cout<<endl;}template<typename T> void turtle_out(vector<vector<T>>& v){for(int i=0;i<int(v.size());++i){turtle_out(v[i]);}}void scan(){}template<typename T,class... Args> void scan(T& n,Args&... args){turtle_in(n);scan(args...);}void print(){}template<typename T,class... Args> void print(T n,Args... args){turtle_out(n);print(args...);}template<typename T> void println(T n){turtle_out(n);cout<<endl;}template<typename T,class... Args> void println(T n,Args... args){turtle_out(n);cout<<" ";println(args...);}template<u64 mod> struct modint{u64 val;modint(i64 val_=0):val((val_%i64(mod)+i64(mod))%i64(mod)){}modint operator-(){return modint(mod-val);}modint operator+(modint rhs){return modint(*this)+=rhs;}modint operator-(modint rhs){return modint(*this)-=rhs;}modint operator*(modint rhs){return modint(*this)*=rhs;}modint operator/(modint rhs){return modint(*this)/=rhs;}modint &operator+=(modint rhs){val+=rhs.val;val-=((val>=mod)?mod:0);return (*this);}modint &operator-=(modint rhs){val+=((val<rhs.val)?mod:0);val-=rhs.val;return (*this);}modint &operator*=(modint rhs){val=val*rhs.val%mod;return (*this);}modint &operator/=(modint rhs){u64 ex=mod-2;modint now=1;while(ex){now*=((ex&1)?rhs:1);rhs*=rhs,ex>>=1;}return (*this)*=now;}bool operator==(modint rhs){return val==rhs.val;}bool operator!=(modint rhs){return val!=rhs.val;}friend std::ostream &operator<<(std::ostream& os,modint x){return os<<(x.val);}friend std::istream &operator>>(std::istream& is,modint& x){u64 t;is>>t,x=t;return is;}};template<typename T,typename U> T power(T a,U n){T res=1;while(n>0){if(n%2==1){res*=a;}a*=a;n/=2;}return res;}template<typename T> struct genrand{uniform_int_distribution<T> gen;mt19937 engine;genrand(T a,T b):gen(a,b){random_device seed_gen;engine.seed(seed_gen());}T operator()(){return gen(engine);}};template<typename T> struct comb{vector<T> dat,idat;comb(int mx=3000000):dat(mx+1,1),idat(mx+1,1){for(int i=1;i<=mx;++i){dat[i]=dat[i-1]*i;}idat[mx]/=dat[mx];for(int i=mx;i>0;--i){idat[i-1]=idat[i]*i;}}T operator()(int n,int k){if(n<0||k<0||n<k){return 0;}return dat[n]*idat[k]*idat[n-k];}};template<typename T> struct matrix{vector<vector<T>> val;int height,width;matrix(int H,int W,T init=0):val(H,vector<T> (W,init)),height(H),width(W){}vector<T> &operator[](int i){return val[i];}matrix operator+(matrix rhs){return matrix(*this)+=rhs;}matrix operator*(matrix rhs){return matrix(*this)*=rhs;}matrix operator+=(matrix rhs){for(int i=0;i<rhs.height;++i){for(int j=0;j<rhs.width;++j){(*this)[i][j]+=rhs[i][j];}}return (*this);}matrix operator*=(matrix rhs){matrix<T> res(height,rhs.width,0);for(int i=0;i<this->height;++i){for(int j=0;j<rhs.width;++j){for(int k=0;k<this->width;++k){res[i][j]+=(*this)[i][k]*rhs[k][j];}}}return (*this)=res;}matrix identity(int n){matrix res(n,n);for(int i=0;i<n;++i){res[i][i]=1;}return res;}matrix mat_pow(i64 k){int n=(*this).height;matrix res=identity(n),now=(*this);while(k>0){if(k%2==1){res*=now;}now*=now;k/=2;}return (*this)=res;}};void solve(){constexpr u64 mod=998244353;typedef modint<mod> mint;i64 N,M,T;scan(N,M,T);vector<vector<int>> G(N);for(int i=0;i<M;++i){int s,t;scan(s,t);G[s].emplace_back(t);G[t].emplace_back(s);}vector<vector<mint>> dp(T+1,vector<mint> (N));dp[0][0]=1;for(int i=0;i<T;++i){for(int j=0;j<N;++j){for(auto v:G[j]){dp[i+1][v]+=dp[i][j];}}}println(dp[T][0]);}