結果

問題 No.1749 ラムドスウイルスの感染拡大
ユーザー ytqm3
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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]);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0