QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#656225 | #9476. 012 Grid | ucup-team5077# | AC ✓ | 128ms | 47940kb | C++14 | 2.9kb | 2024-10-19 11:52:31 | 2024-10-19 11:52:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e5+5,mod=998244353;
void gmod(int &x){
x%=mod;
}
int ksm(int a,int x){
int tot=1;
while(x){
if(x & 1ll) tot=tot*a%mod;
a=a*a%mod;
x>>=1ll;
}
return tot;
}
int mul[N],inv[N];
void init(int lim){
mul[0]=inv[0]=1;
for(int i=1;i<=lim;i++) mul[i]=mul[i-1]*i%mod;
inv[lim]=ksm(mul[lim],mod-2);
for(int i=lim-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int m,int n){
if(m<0 || n<0 || m<n) return 0;
return mul[m]*inv[n]%mod*inv[m-n]%mod;
}
namespace NTT{
int A[N],B[N],C[N];
int rev[N],pre[N];
int init(int n){
int lim=0;
while((1ll<<lim)<=n) lim++;
for(int i=0;i<(1<<lim);i++)
rev[i]=(rev[i>>1] >> 1) | ((i & 1)<<(lim-1));
int omega=ksm(3,(mod-1)/(1<<lim));
pre[0]=1;
for(int i=1;i<=(1<<lim);i++)
pre[i]=pre[i-1]*omega%mod;
return lim;
}
void ntt(int *f,int n,int opt){
for(int i=0;i<n;i++){
if(i<rev[i]) swap(f[i],f[rev[i]]);
}
for(int l=1;l<n;l*=2){
for(int i=0;i<n;i+=l*2){
int u=n/l/2,nw=(opt==1)?0:n;
for(int j=0;j<l;j++){
int x=f[i+j],y=pre[nw]*f[i+j+l]%mod;
gmod(f[i+j]=x+y),gmod(f[i+j+l]=x+mod-y);
nw+=opt*u;
}
}
}
if(opt==-1){
int t=ksm(n,mod-2);
for(int i=0;i<n;i++) f[i]=f[i]*t%mod;
}
}
void solve(int *s,int *f,int *g,int n,int m){
int lim=init(n+m);
for(int i=0;i<=n;i++) A[i]=f[i];
for(int i=0;i<=m;i++) B[i]=g[i];
for(int i=n+1;i<(1<<lim);i++) A[i]=0;
for(int i=m+1;i<(1<<lim);i++) B[i]=0;
ntt(A,1<<lim,1);
ntt(B,1<<lim,1);
for(int i=0;i<(1<<lim);i++) s[i]=A[i]*B[i]%mod;
ntt(s,(1<<lim),-1);
}
}
int n,m;
int F[N],G[N],H[N];
signed main(){
init(N-5);
cin>>n>>m;
int s2=(C(n-1+m-1,n-1)*C(n-1+m-1,n-1)%mod+mod-C(n-2+m,n-2)*C(n+m-2,n)%mod)%mod;
// cout<<s2<<endl;
int s1=0;
for(int i=1;i<n;i++){
gmod(s1+=(C(n-i+m,n-i)*C(n-i-1+m-1,n-i-1)%mod+mod-C(n-i+m-1,n-i)*C(n-i-1+m,n-i-1)%mod)%mod);
}
swap(n,m);
int s4=0;
for(int i=1;i<n;i++){
gmod(s4+=(C(n-i+m,n-i)*C(n-i-1+m-1,n-i-1)%mod+mod-C(n-i+m-1,n-i)*C(n-i-1+m,n-i-1)%mod)%mod);
}
// cout<<s1<<" "<<s4<<endl;
int s5=0;
for(int d=1;d<n;d++){
int c=n-1-d;
gmod(s5+=(C(d-1+m,m)*C(d-1+m,m)%mod+mod-C(d+m,m)*C(d-2+m,m)%mod)%mod*c%mod);
}
swap(n,m);
int s7=0;
for(int d=1;d<n;d++){
int c=n-1-d;
gmod(s7+=(C(d-1+m,m)*C(d-1+m,m)%mod+mod-C(d+m,m)*C(d-2+m,m)%mod)%mod*c%mod);
}
swap(n,m);
int s3=0;
memset(F,0,sizeof(F));
memset(G,0,sizeof(G));
for(int i=1;i<n;i++) F[i]=inv[i]*inv[i-1]%mod;
for(int i=1;i<m;i++) G[i]=inv[i]*inv[i-1]%mod;
NTT::solve(H,F,G,n-1,m-1);
for(int i=2;i<=n+m-2;i++)
gmod(s3+=H[i]*(mul[i]%mod*mul[i-2]%mod+mod-mul[i-1]%mod*mul[i-1]%mod));
int s9=s3;
int ans=s2;
gmod(ans+=(s1+s4)%mod*2%mod);
gmod(ans+=(s5+s7)%mod);
gmod(ans+=(s3+s9)%mod);
cout<<(ans+2)%mod;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 31160kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 3ms
memory: 28092kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 128ms
memory: 47940kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 3ms
memory: 30960kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 10ms
memory: 29472kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 7ms
memory: 30904kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 3ms
memory: 31204kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 5ms
memory: 27732kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 6ms
memory: 30496kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 0ms
memory: 31224kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 6ms
memory: 27696kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 5ms
memory: 31380kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 9ms
memory: 27768kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 4ms
memory: 31696kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 4ms
memory: 30964kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 4ms
memory: 28008kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 8ms
memory: 32788kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 8ms
memory: 30960kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 12ms
memory: 29860kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 4ms
memory: 28328kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 12ms
memory: 29860kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 8ms
memory: 31328kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 4ms
memory: 32744kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 122ms
memory: 45844kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 38ms
memory: 41736kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 40ms
memory: 42696kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 29ms
memory: 38220kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 126ms
memory: 45772kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 47ms
memory: 43232kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 42ms
memory: 42780kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 37ms
memory: 38360kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 33ms
memory: 43340kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 43ms
memory: 41936kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 125ms
memory: 47880kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 120ms
memory: 45824kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 119ms
memory: 45900kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 7ms
memory: 33116kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 19ms
memory: 34512kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 20ms
memory: 37280kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 7ms
memory: 30480kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed