QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87612#4903. 细菌Pure_Furies100 ✓2000ms17444kbC++142.4kb2023-03-13 21:15:092023-03-13 21:15:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-13 21:15:16]
  • 评测
  • 测评结果:100
  • 用时:2000ms
  • 内存:17444kb
  • [2023-03-13 21:15:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
const int maxn=524288;
int mypow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		y>>=1;x=1ll*x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
int fac[maxn],inv[maxn];
int C(int x,int y){
	if(x<y||y<0)return 0;  
	return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
struct node{
	int p,l,r,w;
	void init(){p=0;l=0;r=0;w=1;}
	int calc(int qp,int ql,int qr){
		while(p<qp)w=(2ll*w+C(p,l-1)-C(p,r)+mod)%mod,p++;
		while(l<ql)w=(w-C(p,l++)+mod)%mod;
		while(l>ql)w=(w+C(p,--l))%mod;
		while(r>qr)w=(w-C(p,r--)+mod)%mod;
		while(r<qr)w=(w+C(p,++r))%mod;
		return w;
	}
}w[120003];
const int B=1000;
int dp[2][B+3],d;
void calc(int *f,int n,int p){
	if(n<=B){
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++)
			dp[0][i]=1;
		f[0]=1;
		for(int i=1;i<=d;i++){
			for(int j=0;j<n;j++){
				dp[i&1][j]=(j?dp[i-1&1][j-1]:0)+(j<n-1?dp[i-1&1][j+1]:0);
				if(dp[i&1][j]>=mod)dp[i&1][j]-=mod;
			}f[i]=dp[i&1][p-1];
		}return;
	}else{
		int l=(p-d-n)/(n+1),r=(d+p-1)/(n+1);
		for(int i=l;i<=r;i++)
			w[i-l].init();
		for(int i=0;i<=d;i++)
			for(int j=l;j<=r;j++)
				f[i]=(f[i]+(j%2?mod-1ll:1ll)*w[j-l].calc(i,(i-p+2+j*(n+1))>>1,(i-p+n)+j*(n+1)>>1))%mod;
	}
}
int n,m,k,a,b,c;
int f[maxn],g[maxn],h[maxn];
int main(){
	cin>>d>>n>>m>>k>>a>>b>>c;
	fac[0]=1;
	for(int i=1;i<maxn;i++)
		fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=0;i<maxn;i++)
		inv[i]=mypow(fac[i],mod-2);
	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;
	DFT(f,maxn,1);
	DFT(g,maxn,1);
	DFT(h,maxn,1);
	for(int i=0;i<maxn;i++)
		f[i]=1ll*f[i]*g[i]%mod*h[i]%mod;
	DFT(f,maxn,-1);
	cout<<1ll*f[d]*fac[d]%mod;
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 202ms
memory: 17428kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 201ms
memory: 17360kb

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: 201ms
memory: 16236kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 206ms
memory: 15756kb

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: 379ms
memory: 16996kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 797ms
memory: 17444kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 213ms
memory: 16168kb

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: 220ms
memory: 16652kb

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: 264ms
memory: 17260kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 281ms
memory: 17140kb

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: 566ms
memory: 16008kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 660ms
memory: 17444kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 794ms
memory: 16748kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 920ms
memory: 15904kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 1042ms
memory: 16368kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 1154ms
memory: 16000kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 1402ms
memory: 17204kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 696ms
memory: 15980kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 410ms
memory: 16264kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 314ms
memory: 16352kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 218ms
memory: 16468kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 206ms
memory: 16692kb

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: 735ms
memory: 17188kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 903ms
memory: 16328kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 1113ms
memory: 16536kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 1280ms
memory: 15588kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 1456ms
memory: 16844kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 1665ms
memory: 15728kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 2000ms
memory: 17084kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 923ms
memory: 16772kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 493ms
memory: 17036kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 344ms
memory: 16836kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 217ms
memory: 16692kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

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

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"