結果

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

ソースコード

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

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