QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#663875 | #9476. 012 Grid | rageOfThunder# | AC ✓ | 242ms | 73900kb | C++23 | 3.5kb | 2024-10-21 18:04:50 | 2024-10-21 18:04:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long T,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an,cn,fac[1000001],inv[1000001],st[1000001],u[1000001],t[1000001][3],f[101][101];
char s[1000001];
struct p{long long q,w;}l[1000001],g[1000001];
long long tmp[1000001],tmp1[1000001],tmp2[1000001],id[1000001],lim=(1<<19),G=3,tmp3[1000001],lg;
long long pow_(long long qq,long long ww){long long ee=1;while(ww){if(ww&1) ee*=qq,ee%=mod;qq*=qq,qq%=mod,ww>>=1;}return ee%mod;}
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*f;}
void add(long long qq,long long ww){l[++o].q=ww,l[o].w=h[qq],h[qq]=o;}
long long gcd(long long qq,long long ww){return !ww?qq:gcd(ww,qq%ww);}
long long find(long long qq){return qq==fa[qq]?qq:fa[qq]=find(fa[qq]);}
void merge(long long qq,long long ww){long long f1=find(qq),f2=find(ww);if(f1==f2) return;fa[f1]=f2;}
long long C(long long qq,long long ww){if(qq<0||ww<0||qq<ww) return 0;return fac[qq]*inv[ww]%mod*inv[qq-ww]%mod;}
void ntt(long long *A,long long *B,long long fl)
{
for(int i=0;i<lim;i++) B[i]=A[i];
for(int i=0;i<lim;i++) if(i<id[i]) swap(B[i],B[id[i]]);
for(int i=1;i<lim;i*=2)
{
long long un=pow_(G,(mod-1)/(i*2));
if(fl==-1) un=pow_(un,mod-2);
for(int j=0;j<lim;j+=i*2)
{
long long om=1;
for(int k=0;k<i;k++)
{
long long x=B[j+k],y=B[i+j+k]*om%998244353;
B[j+k]=(x+y)%998244353,B[i+j+k]=(x-y+998244353)%998244353;om=om*un%998244353;
}
}
}
}
int main()
{
// freopen("1.in","r",stdin);
srand((unsigned)(time(0)^(*new int)));
fac[0]=1;for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
inv[1000000]=pow_(fac[1000000],mod-2);for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
scanf("%lld%lld",&a,&b);
for(int i=a-1;i>=1;i--)
{
l[++cn]=p{0,i};
}
for(int i=0;i<b;i++) l[++cn]=p{i,0};
cn=0;
for(int i=1;i<=b;i++) g[++cn]=p{i,a};
for(int i=a-1;i>=1;i--) g[++cn]=p{b,i};
for(int i=1;i<=100;i++)
{
for(int j=1;j<=100;j++)
{
// 0,1~i-1,j
// 1,0~i,j-1
f[i][j]=(C(i+j-2,i-1)*C(i+j-2,i-1)-C(i+j-2,i-2)*C(i+j-2,i))%mod;
}
}
lg=log2(lim);for(int i=0;i<lim;i++) id[i]=(id[i>>1]>>1)+((i&1)<<(lg-1));
for(int i=0;i<=a-2;i++) tmp[i]=inv[i]*inv[i]%mod;
for(int i=0;i<=b-1;i++) tmp1[i]=inv[i]*inv[i]%mod;
ntt(tmp,tmp2,1);ntt(tmp1,tmp3,1);
for(int i=0;i<lim;i++) tmp2[i]=tmp2[i]*tmp3[i]%mod;
ntt(tmp2,tmp3,-1);long long tt=pow_(lim,mod-2);
for(int i=0;i<lim;i++) tmp3[i]=tmp3[i]*tt%mod;
for(int i=0;i<lim;i++) an=(an+tmp3[i]*fac[i]%mod*fac[i]%mod)%mod;
memset(tmp,0,sizeof(tmp));
memset(tmp1,0,sizeof(tmp1));
for(int i=1;i<=a-2;i++) tmp[i]=inv[i-1]*inv[i+1]%mod;
for(int i=1;i<=b-1;i++) tmp1[i]=inv[i-1]*inv[i+1]%mod;
ntt(tmp,tmp2,1);ntt(tmp1,tmp3,1);
for(int i=0;i<lim;i++) tmp2[i]=tmp2[i]*tmp3[i]%mod;
ntt(tmp2,tmp3,-1);tt=pow_(lim,mod-2);
for(int i=0;i<lim;i++) tmp3[i]=tmp3[i]*tt%mod;
for(int i=0;i<lim;i++) an=(an-tmp3[i]*fac[i]%mod*fac[i]%mod)%mod;
// for(int i=0;i<=a-2;i++)
// {
// for(int j=0;j<=b-1;j++)
// {
// an=(an+C(i+j,j)*C(i+j,i)-C(i+j,j-1)*C(i+j,i-1))%mod;
// }
// }
an=an*2%mod;
for(int i=1;i<=b;i++)
{
an=(an+(C(a+i-2,i-1)*C(a+i-2,i-1)-C(a+i-2,i-2)*C(a+i-2,i))%mod*(b-i+1))%mod;
}
for(int i=1;i<=a-2;i++)
{
an=(an+(C(b+i-2,i-1)*C(b+i-2,i-1)-C(b+i-2,i-2)*C(b+i-2,i))%mod*(a-1-i))%mod;
}
an=(an+2)%mod;
printf("%lld",(an%mod+mod)%mod);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 206ms
memory: 58580kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 242ms
memory: 58692kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 212ms
memory: 73100kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 198ms
memory: 59192kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 205ms
memory: 60824kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 204ms
memory: 61768kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 199ms
memory: 60264kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 206ms
memory: 58028kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 210ms
memory: 59948kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 203ms
memory: 60344kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 202ms
memory: 59884kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 208ms
memory: 61036kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 216ms
memory: 60392kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 210ms
memory: 59840kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 213ms
memory: 58564kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 204ms
memory: 59376kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 217ms
memory: 58640kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 204ms
memory: 61736kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 205ms
memory: 61016kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 205ms
memory: 58528kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 211ms
memory: 59968kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 208ms
memory: 59332kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 204ms
memory: 59284kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 216ms
memory: 69400kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 214ms
memory: 63916kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 208ms
memory: 63260kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 218ms
memory: 62276kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 221ms
memory: 71264kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 214ms
memory: 66656kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 193ms
memory: 67684kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 214ms
memory: 64980kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 207ms
memory: 63376kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 208ms
memory: 67728kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 222ms
memory: 73304kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 206ms
memory: 73900kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 215ms
memory: 73036kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 207ms
memory: 59136kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 202ms
memory: 62232kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 207ms
memory: 63596kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 199ms
memory: 59216kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed