QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708809#4903. 细菌TheZone100 ✓1086ms37700kbC++206.9kb2024-11-04 07:14:362024-11-04 07:14:36

Judging History

你现在查看的是最新测评结果

  • [2024-11-04 07:14:36]
  • 评测
  • 测评结果:100
  • 用时:1086ms
  • 内存:37700kb
  • [2024-11-04 07:14:36]
  • 提交

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"