QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#708809 | #4903. 细菌 | TheZone | 100 ✓ | 1086ms | 37700kb | C++20 | 6.9kb | 2024-11-04 07:14:36 | 2024-11-04 07:14:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=1e6+5,B=450,p3=3,inv3=332748118;
int d,n,m,k,a,b,c,f1[N],f2[N],f3[N],g[N],fac[N],inv[N];
int power(int a,int b){int res=1;for(;b;b>>=1){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;}return res;}
void init()
{
fac[0]=1;for(int i=1;i<N;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[N-1]=power(fac[N-1],mod-2);
for(int i=N-2;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
inline int C(int x,int y){if(x<0 || y<0 || x<y)return 0;return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
inline int F(int x,int y){if(x<0 || y<0)return 0;return C(x+y,x);}
bool ck(int x,int y,int i,int a,int b){if(y==x+i*b-(i-1)*a || y==x+(i+1)*b-i*a)return 0;return 1;}
int dp[N];
void solve(int n,int lim,int *f)
{
if(n<=B)
{
for(int i=1;i<=n;i++)dp[i]=1;f[0]=1;
for(int i=1;i<=d;i++)
{
for(int j=1;j<=n;j++)g[j]=0;
for(int j=1;j<=n;j++)
{
if(j>1)g[j-1]=(g[j-1]+dp[j])%mod;
if(j<n)g[j+1]=(g[j+1]+dp[j])%mod;
}
for(int j=1;j<=n;j++)dp[j]=g[j],g[j]=0;
f[i]=dp[lim];
}
}
else
{
int a=lim,b=lim-1-n;
for(int i=1;;i++)
{
int xl=0,yl=i*a-(i-1)*b+1,now=1,xr=xl,yr=yl,len=xl+yl;
bool fl=0;
int stx=0,sty=0;
while(len<=d)
{
fl=1;
if(i&1)f[len]=(f[len]-now+mod)%mod;
else f[len]=(f[len]+now)%mod;
now=2*now%mod;
if(!ck(xl,yl+1,-i,a,b))now=(now-F(xl-stx,yl-sty)+mod)%mod,xl++;else now=(now+F(xl-1-stx,yl+1-sty))%mod,yl++;
if(!ck(xr+1,yr,-i,a,b))now=(now-F(xr-stx,yr-sty)+mod)%mod,yr++;else now=(now+F(xr+1-stx,yr-1-sty))%mod,xr++;
len++;
}
xl=-i*b+(i-1)*a+1,yl=0,now=1,xr=xl,yr=yl,len=xl+yl;
stx=0,sty=0;
while(len<=d)
{
fl=1;
if(i&1)f[len]=(f[len]-now+mod)%mod;
else f[len]=(f[len]+now)%mod;
now=2*now%mod;
if(!ck(xl,yl+1,i,a,b))now=(now-F(xl-stx,yl-sty)+mod)%mod,xl++;else now=(now+F(xl-1-stx,yl+1-sty))%mod,yl++;
if(!ck(xr+1,yr,i,a,b))now=(now-F(xr-stx,yr-sty)+mod)%mod,yr++;else now=(now+F(xr+1-stx,yr-1-sty))%mod,xr++;
len++;
}
if(!fl)break;
}
int xl=0,yl=0,now=1,xr=xl,yr=yl,len=xl+yl;
while(len<=d)
{
f[len]=(f[len]+now)%mod;
now=2*now%mod;
if(!ck(xl,yl+1,0,a,b))now=(now-F(xl,yl)+mod)%mod,xl++;else now=(now+F(xl-1,yl+1))%mod,yl++;
if(!ck(xr+1,yr,0,a,b))now=(now-F(xr,yr)+mod)%mod,yr++;else now=(now+F(xr+1,yr-1))%mod,xr++;
len++;
}
}
}
int g1[N],g2[N];
int X[N],Y[N],r[N],lim,l,Z[N];
void ntt(int *temp,int tp)
{
for(int i=0;i<lim;i++)if(i<r[i])swap(temp[i],temp[r[i]]);
for(int i=1;i<lim;i<<=1)
{
int wn=power(tp,(mod-1)/(i<<1));
for(int j=0;j<lim;j+=(i<<1))
{
int w=1;
for(int k=0;k<i;k++,w=1ll*w*wn%mod)
{
int x=temp[j+k],y=1ll*w*temp[i+j+k]%mod;
temp[j+k]=(x+y)%mod,temp[i+j+k]=(x-y+mod)%mod;
}
}
}
}
void init1(int n)
{
lim=1,l=0;
while(lim<=n)lim<<=1,l++;
for(int i=0;i<lim;i++)r[i]=(r[i>>1]>>1)|((i&1)<<l-1),X[i]=0,Y[i]=0;
}
int main()
{
init();
// freopen("bacteria.in","r",stdin);
// freopen("bacteria.out","w",stdout);
scanf("%d %d %d %d %d %d %d",&d,&n,&m,&k,&a,&b,&c);
solve(n,a,f1),solve(m,b,f2),solve(k,c,f3);
init1(d*2+2);
for(int i=0;i<=d;i++)X[i]=1ll*f1[i]*inv[i]%mod,Y[i]=1ll*f2[i]*inv[i]%mod,Z[i]=1ll*f3[i]*inv[i]%mod;
ntt(X,p3),ntt(Y,p3),ntt(Z,p3);
for(int i=0;i<lim;i++)X[i]=1ll*X[i]*Y[i]%mod*Z[i]%mod;
ntt(X,inv3);
int invl=power(lim,mod-2);
for(int i=0;i<lim;i++)X[i]=1ll*X[i]*invl%mod*fac[i]%mod;
printf("%d\n",X[d]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 13ms
memory: 28520kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 5
Accepted
time: 6ms
memory: 28384kb
input:
50 49 44 48 49 15 25
output:
544847893
result:
ok 1 number(s): "544847893"
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #3:
score: 10
Accepted
time: 7ms
memory: 18284kb
input:
5000 4994 4990 4990 976 2257 2505
output:
836390717
result:
ok 1 number(s): "836390717"
Test #4:
score: 10
Accepted
time: 7ms
memory: 20468kb
input:
5000 4994 4997 4994 4399 1826 1332
output:
65414465
result:
ok 1 number(s): "65414465"
Subtask #3:
score: 15
Accepted
Test #5:
score: 15
Accepted
time: 166ms
memory: 29424kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 15
Accepted
time: 236ms
memory: 29988kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 15
Accepted
time: 71ms
memory: 32072kb
input:
120000 119999 1 1 19896 1 1
output:
68846585
result:
ok 1 number(s): "68846585"
Subtask #4:
score: 10
Accepted
Test #8:
score: 10
Accepted
time: 72ms
memory: 26392kb
input:
119000 119991 119991 1 23819 52139 1
output:
944500934
result:
ok 1 number(s): "944500934"
Subtask #5:
score: 15
Accepted
Dependency #4:
100%
Accepted
Test #9:
score: 15
Accepted
time: 90ms
memory: 26360kb
input:
120000 13997 13996 1 42 9266 1
output:
775637357
result:
ok 1 number(s): "775637357"
Test #10:
score: 15
Accepted
time: 91ms
memory: 30436kb
input:
120000 13997 13997 1 9768 6131 1
output:
151873213
result:
ok 1 number(s): "151873213"
Subtask #6:
score: 35
Accepted
Dependency #3:
100%
Accepted
Dependency #5:
100%
Accepted
Test #11:
score: 35
Accepted
time: 262ms
memory: 37684kb
input:
120000 294 296 1 142 273 1
output:
889786082
result:
ok 1 number(s): "889786082"
Test #12:
score: 35
Accepted
time: 331ms
memory: 37700kb
input:
120000 395 390 1 370 185 1
output:
884557050
result:
ok 1 number(s): "884557050"
Test #13:
score: 35
Accepted
time: 745ms
memory: 26400kb
input:
120000 491 495 1 430 25 1
output:
272929924
result:
ok 1 number(s): "272929924"
Test #14:
score: 35
Accepted
time: 624ms
memory: 26400kb
input:
120000 590 593 1 418 459 1
output:
446962505
result:
ok 1 number(s): "446962505"
Test #15:
score: 35
Accepted
time: 557ms
memory: 32424kb
input:
120000 697 690 1 166 450 1
output:
216092107
result:
ok 1 number(s): "216092107"
Test #16:
score: 35
Accepted
time: 486ms
memory: 26404kb
input:
120000 793 799 1 416 61 1
output:
661260042
result:
ok 1 number(s): "661260042"
Test #17:
score: 35
Accepted
time: 404ms
memory: 26304kb
input:
120000 1000 1000 1 613 547 1
output:
429669083
result:
ok 1 number(s): "429669083"
Test #18:
score: 35
Accepted
time: 236ms
memory: 28328kb
input:
120000 1993 1995 1 493 565 1
output:
609392900
result:
ok 1 number(s): "609392900"
Test #19:
score: 35
Accepted
time: 130ms
memory: 28252kb
input:
120000 4995 4998 1 3166 3765 1
output:
394497547
result:
ok 1 number(s): "394497547"
Test #20:
score: 35
Accepted
time: 100ms
memory: 28460kb
input:
120000 9994 9991 1 6099 691 1
output:
795651799
result:
ok 1 number(s): "795651799"
Test #21:
score: 35
Accepted
time: 70ms
memory: 30460kb
input:
120000 49990 49990 1 41933 2862 1
output:
360787513
result:
ok 1 number(s): "360787513"
Test #22:
score: 35
Accepted
time: 69ms
memory: 30508kb
input:
120000 119996 119994 1 58014 49559 1
output:
682979057
result:
ok 1 number(s): "682979057"
Subtask #7:
score: 10
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #23:
score: 10
Accepted
time: 362ms
memory: 29368kb
input:
120000 296 300 297 89 130 280
output:
702788425
result:
ok 1 number(s): "702788425"
Test #24:
score: 10
Accepted
time: 463ms
memory: 31480kb
input:
120000 392 397 391 222 280 10
output:
322470184
result:
ok 1 number(s): "322470184"
Test #25:
score: 10
Accepted
time: 1086ms
memory: 26876kb
input:
120000 499 498 500 263 315 367
output:
449848666
result:
ok 1 number(s): "449848666"
Test #26:
score: 10
Accepted
time: 920ms
memory: 22656kb
input:
120000 598 591 594 497 474 400
output:
35486519
result:
ok 1 number(s): "35486519"
Test #27:
score: 10
Accepted
time: 800ms
memory: 26692kb
input:
120000 694 692 695 625 173 477
output:
785203749
result:
ok 1 number(s): "785203749"
Test #28:
score: 10
Accepted
time: 708ms
memory: 28840kb
input:
120000 794 796 800 395 465 507
output:
897269426
result:
ok 1 number(s): "897269426"
Test #29:
score: 10
Accepted
time: 574ms
memory: 22724kb
input:
120000 993 998 991 196 712 911
output:
464727191
result:
ok 1 number(s): "464727191"
Test #30:
score: 10
Accepted
time: 313ms
memory: 22740kb
input:
120000 1991 2000 1994 1937 1362 1494
output:
473701811
result:
ok 1 number(s): "473701811"
Test #31:
score: 10
Accepted
time: 169ms
memory: 30136kb
input:
120000 4994 4990 4990 646 1214 2276
output:
763540821
result:
ok 1 number(s): "763540821"
Test #32:
score: 10
Accepted
time: 121ms
memory: 22636kb
input:
120000 9994 9992 9991 6588 9538 2632
output:
804858722
result:
ok 1 number(s): "804858722"
Test #33:
score: 10
Accepted
time: 68ms
memory: 22720kb
input:
120000 49997 49997 49993 46278 44140 26931
output:
139550295
result:
ok 1 number(s): "139550295"
Test #34:
score: 10
Accepted
time: 75ms
memory: 28780kb
input:
120000 119997 120000 120000 24867 116477 35338
output:
946147605
result:
ok 1 number(s): "946147605"