QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#667871 | #9476. 012 Grid | ucup-team3555 | AC ✓ | 127ms | 33712kb | C++14 | 2.2kb | 2024-10-23 09:10:25 | 2024-10-23 09:10:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5,H=998244353;
int n,m,fac[N],ifac[N],ans=0;
int adc(int a,int b){return a+b>=H?a+b-H:a+b;}
int dec(int a,int b){return a<b?a-b+H:a-b;}
int mul(int a,int b){return 1ll*a*b%H;}
void add(int &a,int b){a=adc(a,b);}
void del(int &a,int b){a=dec(a,b);}
int qpow(int a,int b=H-2){
int res=1;
while(b){if(b&1) res=mul(res,a);a=mul(a,a),b>>=1;}
return res;
}
namespace Poly{
#define poly vector<int>
int U[N<<2],P,w[N<<2];
const int g=3,ig=qpow(g);
void Init(int n){
for(int i=1;i<=n;i++) U[i]=(U[i>>1]>>1)|((i&1)?n>>1:0);
}
void Cro(poly &F,poly G){
for(int i=0;i<(int)F.size();i++) F[i]=mul(F[i],G[i]);
}
void NTT(poly &p,int len,int op){
for(int i=0;i<len;i++) if(i<U[i]) swap(p[i],p[U[i]]);
int u,tmp;w[0]=1;
for(int k=2,lst=1;k<=len;lst=k,k<<=1){
u=qpow(op==1?g:ig,(H-1)/k);
for(int i=1;i<=lst;i++) w[i]=mul(w[i-1],u);
for(int i=0;i<len;i+=k)
for(int l=i;l<i+lst;l++)
tmp=mul(p[l+lst],w[l-i]),p[l+lst]=dec(p[l],tmp),add(p[l],tmp);
}
if(op==-1){
int I=qpow(len);
for(int i=0;i<len;i++) p[i]=mul(p[i],I);
}
}
poly operator *(poly F,poly G){
int n=(int)F.size(),m=(int)G.size();
for(P=1;P<n+m;P<<=1);
Init(P),F.resize(P),G.resize(P);
NTT(F,P,1),NTT(G,P,1),Cro(F,G),NTT(F,P,-1);
F.resize(n+m-1);return F;
}
}
using namespace Poly;
void init(int n){
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
ifac[n]=qpow(fac[n]);
for(int i=n;i>=1;i--) ifac[i-1]=mul(ifac[i],i);
}
int calc(int x,int y){
return mul(mul(fac[x+y-1],fac[x+y-2]),mul(mul(ifac[x],ifac[y]),mul(ifac[x-1],ifac[y-1])));
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
init(n+m);
poly F(n+m-1),G(n+m-1);
for(int i=1;i<=n-1;i++) F[i]=mul(ifac[i],ifac[i-1]);
for(int i=1;i<=m-1;i++) G[i]=mul(ifac[i],ifac[i-1]);
F=F*G;
for(int i=2;i<=n+m-2;i++) add(ans,mul(mul(fac[i-1],fac[i-2]),F[i]));
ans=adc(mul(ans,2),2);
for(int j=1;j<=m;j++) add(ans,mul(calc(n,j),m-j+1));
for(int i=1;i<n;i++) add(ans,mul(calc(i,m),n-i+1));
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9676kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 2ms
memory: 9668kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 117ms
memory: 31772kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 2ms
memory: 9912kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 2ms
memory: 9668kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 0ms
memory: 9736kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 0ms
memory: 9728kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 2ms
memory: 9676kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 0ms
memory: 9672kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 0ms
memory: 9668kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 2ms
memory: 9684kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 0ms
memory: 9912kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 5ms
memory: 10216kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 4ms
memory: 10244kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 5ms
memory: 10204kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 4ms
memory: 9960kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 0ms
memory: 9932kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 0ms
memory: 10032kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 2ms
memory: 12260kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 5ms
memory: 9936kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 5ms
memory: 10248kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 5ms
memory: 10044kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 117ms
memory: 33064kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 52ms
memory: 20772kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 48ms
memory: 20524kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 25ms
memory: 13672kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 117ms
memory: 33136kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 54ms
memory: 20736kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 49ms
memory: 21616kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 51ms
memory: 20784kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 51ms
memory: 20940kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 49ms
memory: 21684kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 111ms
memory: 31580kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 110ms
memory: 33504kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 127ms
memory: 33712kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 0ms
memory: 9632kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 25ms
memory: 17684kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 24ms
memory: 13508kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 2ms
memory: 9636kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed