結果
問題 | 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";}}