QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#400652#4903. 细菌Dawnq100 ✓1957ms18560kbC++142.6kb2024-04-27 14:40:102024-04-27 14:40:10

Judging History

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

  • [2024-04-27 14:40:10]
  • 评测
  • 测评结果:100
  • 用时:1957ms
  • 内存:18560kb
  • [2024-04-27 14:40:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5,mod=998244353,B=5000,G=3,lim=1<<19;
int d,n,m,k,a,b,c;
int dp[2][5005],f[N],g[N],h[N],fac[N],inv[N],rev[N],w[N]={1};
inline int Add(int x,int y){return x+y-mod*(x+y>=mod);}
inline int qpow(int x,int y){
	int Res=1;while(y){
		if(y&1)Res=1ll*Res*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}return Res;
}
inline int C(int x,int y){return x<0||y<0||x<y?0:1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
inline void pre(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
	for(int i=1;i<n;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<18);
}
inline void NTT(int n,int *a,int op){
	for(int i=1;i<n;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int l=1;l<<1<=n;l<<=1){
		int W=qpow(G,(mod-1)/(l<<1));
		for(int i=1;i<l;++i)w[i]=1ll*w[i-1]*W%mod;
		for(int i=0;i+(l<<1)<=n;i+=l<<1){
			for(int j=0;j<l;++j){
				int x=a[i+j],y=1ll*a[i+j+l]*w[j]%mod;
				a[i+j]=Add(x,y),a[i+j+l]=Add(x,mod-y);
			}
		}
	}
	if(op==-1){
		int inv=qpow(n,mod-2);
		reverse(a+1,a+n);
		for(int i=0;i<n;++i)a[i]=1ll*a[i]*inv%mod;
	}
}
struct Cx{
	int i,l,r,Res;
	inline void pre(){i=l=r=0,Res=1;}
	inline int ask(int I,int ql,int qr){
		for(;i<I;++i){
			Res=2ll*Res%mod;
			Res=Add(Res,C(i,l-1));
			Res=Add(Res,mod-C(i,r));
		}
		while(l<ql)Res=Add(Res,mod-C(i,l)),++l;
		while(r>qr)Res=Add(Res,mod-C(i,r)),--r;
		while(l>ql)--l,Res=Add(Res,C(i,l));
		while(r<qr)++r,Res=Add(Res,C(i,r));
		return Res;
	}
}cx[N];
inline void Calc(int *f,int n,int a){
	if(n<=B){
		memset(dp,0,sizeof(dp));
		int now=1,pre=0;
		f[0]=1;
		for(int i=1;i<=n;++i)dp[now][i]=1;
		for(int i=1;i<=d;++i){
			now^=1,pre^=1;
			for(int j=1;j<=n;++j){
				dp[now][j]=0;
				if(j!=1)dp[now][j]=Add(dp[now][j],dp[pre][j-1]);
				if(j!=n)dp[now][j]=Add(dp[now][j],dp[pre][j+1]);
			}
			f[i]=dp[now][a];
		}
	}else{
		++n;
		int l=(a-d-n+1)/n,r=(a+d-1)/n;
		for(int i=l;i<=r;++i)cx[i-l].pre();
		for(int i=0;i<=d;++i){
			for(int j=l;j<=r;++j){
				int ql=(i+j*n-a+2)>>1,qr=(i+n+j*n-a-1)>>1;
				f[i]=Add(f[i],(j&1?mod-1ll:1ll)*cx[j-l].ask(i,ql,qr)%mod);
			}
		}
	}
}
signed main(){
//	freopen("bacteria.in","r",stdin);
//	freopen("bacteria.out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>d>>n>>m>>k>>a>>b>>c;
	pre(lim),Calc(f,n,a),Calc(g,m,b),Calc(h,k,c);
	for(int i=0;i<=d;++i)f[i]=1ll*f[i]*inv[i]%mod,g[i]=1ll*g[i]*inv[i]%mod,h[i]=1ll*h[i]*inv[i]%mod;
	NTT(lim,f,1),NTT(lim,g,1),NTT(lim,h,1);
	for(int i=0;i<lim;++i)f[i]=1ll*f[i]*g[i]%mod*h[i]%mod;
	NTT(lim,f,-1);
	cout<<1ll*f[d]*fac[d]%mod;
	return 0;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 71ms
memory: 18428kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 75ms
memory: 18424kb

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: 149ms
memory: 18388kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 154ms
memory: 18560kb

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: 111ms
memory: 18432kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 203ms
memory: 18488kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 71ms
memory: 18140kb

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: 79ms
memory: 17972kb

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: 116ms
memory: 17856kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 130ms
memory: 17908kb

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: 152ms
memory: 18500kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 175ms
memory: 18492kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 196ms
memory: 18496kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 222ms
memory: 18548kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 253ms
memory: 18504kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 272ms
memory: 18504kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 329ms
memory: 18428kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 573ms
memory: 18428kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 1318ms
memory: 18556kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 155ms
memory: 17848kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 88ms
memory: 17916kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 78ms
memory: 17908kb

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: 197ms
memory: 18512kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 225ms
memory: 18492kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 271ms
memory: 18520kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 300ms
memory: 18500kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 334ms
memory: 18488kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 373ms
memory: 18428kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 467ms
memory: 18492kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 814ms
memory: 18508kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 1957ms
memory: 18436kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 192ms
memory: 17808kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 95ms
memory: 17808kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

score: 0
Accepted
time: 80ms
memory: 17836kb

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"