#718132 (C++14) No.1750 ラムドスウイルスの感染拡大-hard

提出ソース

結果

問題	No.1750 ラムドスウイルスの感染拡大-hard
ユーザー	bt yamato
提出日時	2021-11-19 22:56:06
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,879 ms / 2,000 ms
コード長	9,775 bytes
コンパイル時間	2,085 ms
コンパイル使用メモリ	181,744 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-10 10:17:52
合計ジャッジ時間	19,500 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	38 ms 6,944 KB
testcase_05	AC	1 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	169 ms 6,944 KB
testcase_09	AC	151 ms 6,940 KB
testcase_10	AC	177 ms 6,940 KB
testcase_11	AC	189 ms 6,944 KB
testcase_12	AC	275 ms 6,940 KB
testcase_13	AC	277 ms 6,944 KB
testcase_14	AC	1,810 ms 6,944 KB
testcase_15	AC	1,879 ms 6,944 KB
testcase_16	AC	1,872 ms 6,944 KB
testcase_17	AC	1,313 ms 6,944 KB
testcase_18	AC	1,196 ms 6,944 KB
testcase_19	AC	1,226 ms 6,940 KB
testcase_20	AC	1,053 ms 6,940 KB
testcase_21	AC	1,509 ms 6,940 KB
testcase_22	AC	246 ms 6,940 KB
testcase_23	AC	1,850 ms 6,940 KB
testcase_24	AC	187 ms 6,944 KB
testcase_25	AC	424 ms 6,940 KB
testcase_26	AC	147 ms 6,944 KB
testcase_27	AC	4 ms 6,940 KB
testcase_28	AC	8 ms 6,940 KB
testcase_29	AC	3 ms 6,944 KB
testcase_30	AC	251 ms 6,940 KB
testcase_31	AC	244 ms 6,940 KB
testcase_32	AC	231 ms 6,940 KB
testcase_33	AC	222 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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=0
        REP(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 reduction
        REP(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.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>N>>M>>T;
    assert(N <= 100);
    assert(M <= min(N*(N-1)/2, 1000LL));
    MAT<mint> A(N,N), ans(N,1);
    REP(i,M)
    {  
        int s = 0,t = 0;
        cin>>s>>t;
        A[s][t] = 1;
        A[t][s] = 1;
    }
    ans[0][0] = 1;
    ans = npow(A,T)*ans;
    cout << ans[0][0] <<endl;
}

yukicoder

結果

テストケース

ソースコード