結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
|
提出日時 | 2021-11-19 22:37:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,948 ms / 2,000 ms |
コード長 | 9,638 bytes |
コンパイル時間 | 1,937 ms |
コンパイル使用メモリ | 175,660 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-01 19:50:40 |
合計ジャッジ時間 | 20,128 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)#define rep(i,a,b) for(int i=int(a);i<int(b);++i)#define All(x) (x).begin(),(x).end()#define rAll(x) (x).rbegin(),(x).rend()using namespace std;using ll = long long;constexpr ll mod = 998244353;class mint {private:ll _num,_mod = mod;mint set(ll num){_num = num ;if(_num<0){if(_num>=-_mod)_num=_mod+_num;else _num=_mod-(-_num)%_mod;}else if(_num>=_mod) _num%=_mod;return *this;}ll imod()const{ll n=_mod-2;ll ans = 1,x=_num;while(n != 0){if(n&1) ans = ans*x%_mod;x = x*x%_mod;n = n >> 1;}return ans;}public:explicit mint(){ _num = 0; }explicit mint(ll num){_num = num;if(_num<0){if(_num>=-_mod)_num=_mod+_num;else _num=_mod-(-_num)%_mod;}else if(_num>=_mod) _num%=_mod;}explicit mint(ll num,ll M){_mod=M;_num=num;if(_num<0){if(_num>=-_mod)_num=_mod+_num;else _num=_mod-(-_num)%_mod;}else if(_num>=_mod) _num%=_mod;}mint(const mint &cp){_num=cp._num;_mod=cp._mod;}mint operator+ (const mint &x)const{ return mint(_num + x._num , _mod); }mint operator- (const mint &x)const{ return mint(_num - x._num , _mod);}mint operator* (const mint &x)const{ return mint(_num * x._num , _mod); }mint operator/ (const mint &x)const{ return mint(_num * x.imod() , _mod);}mint operator+=(const mint &x){ return set(_num + x._num); }mint operator-=(const mint &x){ return set(_num - x._num); }mint operator*=(const mint &x){ return set(_num * x._num); }mint operator/=(const mint &x){ return set(_num * x.imod());}mint operator= (const ll x){ return set(x); }mint operator+ (const ll x)const{return *this + mint(x,_mod); }mint operator- (const ll x)const{ return *this - mint(x,_mod); }mint operator* (const ll x)const{ return *this * mint(x,_mod); }mint operator/ (const ll x)const{ return *this/mint(x, _mod);}mint operator+=(const ll x){ *this = *this + x;return *this; }mint operator-=(const ll x){ *this = *this - x;return *this; }mint operator*=(const ll x){ *this = *this * x;return *this;}mint operator/=(const ll x){ *this = *this / x;return *this;}bool operator==(const mint &x)const{return _num==x._num;}bool operator!=(const mint &x)const{return _num!=x._num;}friend mint operator+(ll x,const mint &m){return mint(m._num + x , m._mod);}friend mint operator-(ll x,const mint &m){return mint( x - m._num , m._mod);}friend mint operator*(ll x,const mint &m){return mint(m._num * (x % m._mod) , m._mod);}friend mint operator/(ll x,const mint &m){return mint(m.imod() * (x % m._mod) , m._mod);}explicit operator ll() { return _num; }explicit operator int() { return (int)_num; }friend std::ostream& operator<<(std::ostream &os, const mint &x){ os << x._num; return os; }friend std::istream& operator>>(std::istream &is, mint &x){ll val; is>>val; x.set(val); return is;}};template<typename T> class MAT{private:int row,col;vector<vector<T>> _A;double eps = 1e-9;MAT set(vector<vector<T>> A){_A = A ; return *this;}public:MAT(){ }MAT(int n,int m=0,T x=T(0)){if(n<1 || m<0){cout << "err Matrix::Matrix" <<endl;exit(1);}row = n;col = m?m:n;//return E if m=0REP(i,row){vector<T> a(col,x);_A.push_back(a);}if(m==0) REP(i,n) _A[i][i]=1.0;}MAT(vector<vector<T>> A){row=A.size();col=A[0].size();_A=A;}MAT(const MAT &cp){_A=cp._A;row=cp.row;col=cp.col;}T* operator[] (int i){return _A[i].data();}MAT operator= (vector<vector<T>> x) {return set(x);}MAT operator+ (MAT x) const {if(row!=x.row || col!=x.col){cerr << "err Matrix::operator+" <<endl;cerr << " not equal matrix size" <<endl;exit(0);}MAT r(row, col);REP(i,row) REP(j,col) r[i][j]=_A[i][j]+x[i][j];return r;}MAT operator- (MAT x) const {if(row!=x.row || col!=x.col){cerr << "err Matrix::operator-" <<endl;cerr << " not equal matrix size" <<endl;exit(0);}MAT r(row, col);REP(i,row) REP(j,col) r[i][j]=_A[i][j]-x[i][j];return r;}MAT operator* (MAT x) const {if(x.col==1&&x.row==1) return x[0][0]*MAT(_A);if(row==1&&col==1) return _A[0][0]*x;if(col!=x.row){cerr << "err Matrix::operator*" <<endl;cerr << " not equal matrix size" <<endl;exit(0);}MAT r(row, x.col);REP(i,row) REP(j,x.col) REP(k,col) r[i][j]+=_A[i][k]*x[k][j];return r;}MAT operator/(MAT x)const{*this = *this * x.inverse(); return *this;}MAT operator/ (T a)const{MAT r(row,col);REP(i,row) REP(j,col) r[i][j]=_A[i][j]/a;return r;}MAT operator+= (MAT x) {*this = *this + x;return *this;}MAT operator-= (MAT x) {*this = *this - x; return *this;}MAT operator*=(T a){*this = a*(*this); return this;}MAT operator/=(MAT x){*this = *this/x;return *this;}MAT operator/=(T a){*this = *this/a; return *this;}friend MAT operator* (T n,MAT x){MAT r(x.row,x.col);REP(i,x.row) REP(j,x.col) r[i][j]=n*x[i][j];return r;}friend MAT operator* (MAT x,T n){MAT r(x.row,x.col);REP(i,x.row) REP(j,x.col) r[i][j]=n*x[i][j];return r;}explicit operator vector<vector<T>>(){return _A;}friend ostream &operator<<(ostream &os,const MAT &x){ REP(i,x.row) REP(j,x.col) os<<x._A[i][j]<<" \n"[j==x.col-1]; return os;}friend istream &operator>>(istream &is,MAT &x){REP(i,x.row) REP(j,x.col) is>>x._A[i][j];return is;}size_t size_row()const{return row;}size_t size_col()const{return col;}MAT transpose()const{MAT r(col,row);REP(i,col) REP(j,row) r[i][j]=_A[j][i];return r;}MAT inverse()const{T buf;MAT<T> inv_a(row,0);vector<vector<T>> a=_A;//row reductionREP(i,row){buf=1/a[i][i];REP(j,row){a[i][j]*=buf;inv_a[i][j]*=buf;}REP(j,row){if(i!=j){buf=a[j][i];REP(k,row){a[j][k]-=a[i][k]*buf;inv_a[j][k]-=inv_a[i][k]*buf;}}}}return inv_a;}MAT Jacobi(MAT b)const{//ヤコビ法によって解を求めるsize_t sz=row;MAT D(sz,sz),inD(sz,sz),H(sz,sz),N(sz,sz);MAT c(sz,1),x(sz,1),tmp(sz,1);//cout<<"initialized"<<endl;REP(i,sz){//値の初期化、Aを対角要素とそれ以外に分解する(できてる)REP(j,sz){H[i][j] = 0;if(i==j){D[i][j] = _A[i][j];inD[i][j] = 1/_A[i][j];N[i][j]=0;}else if(i!=j){D[i][j] = 0;inD[i][j] = 0;N[i][j]=_A[i][j];}}c[i][0] = 0;x[i][0] = 1;}c=inD*b;H=inD*N;while(1){//反復法ステップ1→2→1...tmp=x;x=c-H*x;T r=T(0);for(int i=0;i<row;++i){r+=(x[i][0]-tmp[i][0])*(x[i][0]-tmp[i][0]);}if(r<eps) break;}return x;}MAT Gauss(MAT b)const{//ガウス・ザイデル法によって解を求めるMAT<T> DL(row),U(row),inDL(row),H(row),c(row,1),x(row,1),tmp(row,1);for(int i=0;i<row;i++){for(int j=0;j<col;j++){H[i][j] = 0;if(i>=j){DL[i][j] = _A[i][j];U[i][j] = 0;}else{DL[i][j] = 0;U[i][j] = _A[i][j];}}x[i][0] = 1;}inDL=DL.inverse();c=inDL*b;H=inDL*U;int n=0;while(1){tmp=x;x=c-H*x;T r = T(0);for(int i=0;i<row;++i){r+=(x[i][0]-tmp[i][0])*(x[i][0]-tmp[i][0]);}n++;if(r<eps) break;}return x;}int rank()const{// O( n^3 )vector<vector<T>> A=_A;const int n = row, m = col;int r = 0;for(int i = 0; r < n && i < m; ++i) {int pivot = r;for(int j = r+1; j < n; ++j) if(fabs(A[j][i]) > fabs(A[pivot][i])) pivot = j;swap(A[pivot], A[r]);if(fabs(A[r][i]) < eps) continue;for (int k = m-1; k >= i; --k) A[r][k] /= A[r][i];rep(j,r+1,n) rep(k,i,m) A[j][k] -= A[r][k] * A[j][i];++r;}return r;}};template<typename T> T npow(T x, ll n){T ans(x.size_col());while(n != 0){if(n&1) ans = ans*x;x = x*x;n = n >> 1;}return ans;}int main(){ll N,M,T;cin>>N>>M>>T;MAT<mint> A(N,N), ans(N,1);REP(i,M){int s,t;cin>>s>>t;A[s][t] = A[t][s] = 1;}ans[0][0] = 1;ans = npow(A,T)*ans;cout << ans[0][0] <<endl;}