結果
問題 | No.2503 Typical Path Counting Problem on a Grid |
ユーザー |
|
提出日時 | 2023-10-13 22:35:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 561 ms / 2,000 ms |
コード長 | 2,467 bytes |
コンパイル時間 | 948 ms |
コンパイル使用メモリ | 79,236 KB |
実行使用メモリ | 316,100 KB |
最終ジャッジ日時 | 2024-09-15 18:20:46 |
合計ジャッジ時間 | 7,541 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cassert> #include<atcoder/modint> using namespace std; #include<array> template<typename T,unsigned int N> struct Matrix{ array<array<T,N>,N>dat; array<T,N>&operator[](int i){return dat[i];} const array<T,N>&operator[](int i)const{return dat[i];} Matrix(){for(int i=0;i<N;i++)dat[i].fill(T(0));} static Matrix eye(){ Matrix res; for(int i=0;i<N;i++)res[i][i]=1; return res; } Matrix operator+(const Matrix&A)const{ Matrix res; for(int i=0;i<N;i++)for(int j=0;j<N;j++) res[i][j]=dat[i][j]+A[i][j]; return res; } Matrix operator*(const Matrix&A)const{ Matrix res; for(int i=0;i<N;i++)for(int k=0;k<N;k++)for(int j=0;j<N;j++) res[i][j]+=dat[i][k]*A[k][j]; return res; } Matrix pow(long long n)const{ Matrix a=*this,res=eye(); for(;n;a=a*a,n>>=1)if(n&1)res=res*a; return res; } }; using mint=atcoder::modint998244353; using mat=Matrix<mint,2>; mint naive(long N,long M) { if(N>M)swap(N,M); assert(N<=M); auto f=[](long NM,long N,long M) { if(N>M)swap(N,M); if(NM<0)return 0L; else if(NM<=N)return NM+1; else if(NM<=M)return N+1L; else if(NM<=N+M)return N+M-NM+1; else return 0L; }; mint cur=1,cur2=0; for(long i=1;i<=N+M;i++) { mint now=0; now+=cur*(f(i-1,N-1,M)+f(i-1,N,M-1)); now+=cur2*f(i-2,N-1,M-1); cur2=cur; cur=now; } return cur; } mint naive2(long N,long M) { if(N>M)swap(N,M); assert(N<=M); mat E=mat::eye(); for(int i=0;i<N+M;i++) { mat A; A[0][0]=i<N?(i+1)*2:i>=M?(N+M-i)*2:N*2+1; A[0][1]=i<N?i:i>=M?N+M-i:N; A[1][0]=1; E=A*E; } return E[0][0]; } mat L[10000001],R[10000001]; mint solve(long N,long M) { if(N>M)swap(N,M); assert(N<=M); assert(N<=10000000); mat E=mat::eye(); E=L[N]*E; mat A; A[0][0]=N*2+1; A[0][1]=N; A[1][0]=1; E=A.pow(M-N)*E; E=R[N]*E; return E[0][0]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); L[0]=mat::eye(); R[0]=mat::eye(); for(int i=1;i<=10000000;i++) { mat A; A[0][0]=mint::raw(i*2); A[0][1]=mint::raw(i-1); A[1][0]=mint::raw(1); L[i]=A*L[i-1]; A[0][1]=mint::raw(i); R[i]=R[i-1]*A; } /* for(long N=0;N<=20;N++)for(long M=0;M<=20;M++) { mint A=naive(N,M),B=solve(N,M); if(A!=B) { cout<<"WA on (N, M) = ("<<N<<", "<<M<<")"<<endl; cout<<"naive = "<<A.val()<<" naive2 = "<<B.val()<<endl; return 1; } } return 0; */ int T;cin>>T; for(;T--;) { long N,M; cin>>N>>M; cout<<solve(N,M).val()<<"\n"; } }