QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#670454 | #9476. 012 Grid | ucup-team902# | AC ✓ | 88ms | 20392kb | C++17 | 3.0kb | 2024-10-23 21:47:50 | 2024-10-23 21:47:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1<<19;
const int mod=998244353;
using arr=int[N+5];
int add(int x,int y){ return (x+=y)>=mod?x-mod:x; }
int sub(int x,int y){ return (x-=y)<0?x+mod:x; }
void red(int &x){ x+=x>>31&mod;}
int ksm(ll x,int tp,int s=1){
for(;tp;x=x*x%mod,tp>>=1) if(tp&1) s=x*s%mod;
return s;
}
int fac[N+5],ifac[N+5];
void prep(){
fac[0]=1;
for(int i=1;i<=N;i++) fac[i]=1ll*fac[i-1]*i%mod;
ifac[N]=ksm(fac[N],mod-2);
for(int i=N;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
}
int C(int n,int m){ return n<0||m<0||n<m?0:1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod; }
namespace poly_base{
int l,n,iv; arr g;
void r_prep(int tl){
int i;
l=(int)log2(tl-1)+1; n=1<<l;
g[0]=1; g[n]=ksm(31,1<<21-l);
for(i=l;i;i--) g[1<<i-1]=1ll*g[1<<i]*g[1<<i]%mod;
for(i=0;i<n;i++) g[i]=1ll*g[i&i-1]*g[i&-i]%mod;
}
void prep(int tl){ n=1<<(l=(int)log2(tl-1)+1); iv=mod-(mod-1)/n; }
void DIT(arr T){
int i,*t,*j,*k,v;
for(i=n>>1;i;i>>=1)
for(t=g,j=T;j!=T+n;j+=i<<1,++t)
for(k=j;k!=j+i;++k)
v=1ll**t*k[i]%mod,red(k[i]=*k-v),red(*k+=v-mod);
}
void DIF(arr T){
int i,*t,*j,*k,v;
for(i=1;i<n;i<<=1)
for(t=g,j=T;j!=T+n;j+=i<<1,++t)
for(k=j;k!=j+i;++k)
red(v=*k+k[i]-mod),k[i]=1ll**t*(*k-k[i]+mod)%mod,*k=v;
reverse(T+1,T+n);
for(int i=0;i<n;i++) T[i]=1ll*T[i]*iv%mod;
}
void NTT(arr a){ DIT(a); }
void INTT(arr a){ DIF(a); }
void NTT(arr a,arr b){ memcpy(b,a,n*sizeof(int)); DIT(b); }
void INTT(arr a,arr b){ memcpy(b,a,n*sizeof(int)); DIF(b); }
}
namespace poly{
using namespace poly_base;
arr pa,pb,pc,pd,pe,pf;
#define szf sizeof(int)
void cl(arr a){ memset(a,0,n*szf); }
void Mult(int t,arr a,arr b,arr c){
if(t==1){ *c=1ll**a**b%mod; return; }
prep(t); NTT(a,c); NTT(b,pa);
for(int i=0;i<n;i++) c[i]=1ll*c[i]*pa[i]%mod;
INTT(c); cl(pa);
}
}
int h,w;
int ans;
arr f,g,res;
int work(int a,int b){
return ((1ll*C(a+b-2,a-1)*C(a+b-2,b-1)-1ll*C(a+b-2,a)*C(a+b-2,b))%mod+mod)%mod;
}
void calc(int h,int w){
for(int i=1;i<h;i++)
ans=(ans+1ll*(h-i-1)*work(w,i))%mod;
}
int main(){
prep();
poly_base::r_prep(N);
scanf("%d %d",&h,&w);
for(int i=0;i<h;i++)
f[i]=1ll*ifac[i]*ifac[i]%mod;
for(int i=0;i<w;i++)
g[i]=1ll*ifac[i]*ifac[i]%mod;
poly::Mult(h+w,f,g,res);
for(int i=0;i<h+w;i++)
ans=(ans+1ll*fac[i]%mod*fac[i]%mod*res[i])%mod;
memset(f,0,sizeof f);
memset(g,0,sizeof g);
memset(res,0,sizeof res);
for(int i=1;i<h;i++)
f[i]=1ll*ifac[i+1]*ifac[i-1]%mod;
for(int i=1;i<w;i++)
g[i]=1ll*ifac[i+1]*ifac[i-1]%mod;
poly::Mult(h+w,f,g,res);
for(int i=0;i<h+w;i++)
ans=(ans-1ll*fac[i]%mod*fac[i]%mod*res[i])%mod;
red(ans);
// for(int i=1;i<=h;i++)
// for(int j=1;j<=w;j++)
// ans=add(ans,work(i,j));
ans=add(ans,ans);
calc(h,w);
calc(w,h);
ans=sub(ans,work(h,w));
ans=add(ans,2);
printf("%d\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 20384kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 6ms
memory: 20196kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 87ms
memory: 20240kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 4ms
memory: 20300kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 9ms
memory: 20208kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 6ms
memory: 20328kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 9ms
memory: 20324kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 9ms
memory: 20384kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 3ms
memory: 20360kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 4ms
memory: 20388kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 9ms
memory: 20392kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 6ms
memory: 20296kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 6ms
memory: 20240kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 11ms
memory: 20240kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 3ms
memory: 20308kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 0ms
memory: 20180kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 11ms
memory: 20320kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 11ms
memory: 20196kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 5ms
memory: 20308kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 7ms
memory: 20384kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 7ms
memory: 20316kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 11ms
memory: 20324kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 7ms
memory: 20196kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 77ms
memory: 20364kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 44ms
memory: 20256kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 39ms
memory: 20304kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 22ms
memory: 20240kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 88ms
memory: 20324kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 45ms
memory: 20208kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 40ms
memory: 20324kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 39ms
memory: 20328kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 39ms
memory: 20256kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 44ms
memory: 20360kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 86ms
memory: 20324kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 86ms
memory: 20392kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 86ms
memory: 20392kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 6ms
memory: 20300kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 17ms
memory: 20308kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 22ms
memory: 20360kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 10ms
memory: 20388kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed