QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#400672#4903. 细菌zwh2008100 ✓845ms19164kbC++142.4kb2024-04-27 14:56:142024-04-27 14:56:14

Judging History

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

  • [2024-04-27 14:56:14]
  • 评测
  • 测评结果:100
  • 用时:845ms
  • 内存:19164kb
  • [2024-04-27 14:56:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
#define fi first
#define se second
const int N=3e5+5,mod=998244353;
int A,B,C,X,Y,Z,k,rev[N];
ll ans,i3,fx[N],fy[N],fz[N],fc[N],inv[N],f[2][N];
ll qp(ll a,int b){ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
void init(int n) {
	fc[0]=1,i3=qp(3,mod-2);for(int i=1;i<=n;i++)fc[i]=fc[i-1]*i%mod;
	inv[n]=qp(fc[n],mod-2);for(int i=n-1;~i;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
ll comb(int n,int m){return n<m||m<0?0:fc[n]*inv[n-m]%mod*inv[m]%mod;}
inline ll md(ll x){return x<mod?x:x-mod;}
void NTT(ll*a,int l,int op) {
	for(int i=0;i<l;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int i=1;i<l;i<<=1) {
		ll wn=qp(op?3:i3,(mod-1)/(i<<1));
		for(int j=0;j<l;j+=i<<1) {
			ll w=1,x,y;
			for(int k=0;k<i;k++,w=w*wn%mod)x=a[j+k],y=a[i+j+k]*w%mod,a[j+k]=md(x+y),a[i+j+k]=md(x-y+mod);
		}
	}
}
void slv(ll*a,int n,int m) {
	auto doit=[&](int l,int r,int op) {
		int L=0,R=-1;ll s=0;
		for(int i=0;i<=k;i++) {
			int nl=max(0,(int)ceil((i+m-r)/2.0)),nr=min(i,(int)floor((i+m-l)/2.0));
			s=(s*2+comb(i-1,L-1)-comb(i-1,R)+mod)%mod;
			if(nl>nr)continue;
			while(R<nr)s=(s+comb(i,++R))%mod;
			while(L<nl)s=(s+mod-comb(i,L++))%mod;
			a[i]=(a[i]+op*s+mod)%mod;
		}
	};
	if(1ll*n*k<=3e8) {
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)f[0][i]=1;
		a[0]=1;
		for(int i=1;i<=k;a[i]=(a[i]+f[i&1][m])%mod,i++)
			for(int j=1;j<=n;j++)f[i&1][j]=(f[i-1&1][j-1]+f[i-1&1][j+1])%mod;
	}else {
		int l=1,r=n;doit(l,r,1);
		for(int o=1;;o++) {
			if(o&1)swap(l,r),l=-l,r=-r;else swap(l,r),l=2*(n+1)-l,r=2*(n+1)-r;
			if(l>3*max(n,k)||r<-3*max(n,k))break;
			doit(l,r,(o&1?-1:1));
		}l=1,r=n;
		for(int o=0;;o++) {
			if(o&1)swap(l,r),l=-l,r=-r;else swap(l,r),l=2*(n+1)-l,r=2*(n+1)-r;
			if(l>3*max(n,k)||r<-3*max(n,k))break;
			doit(l,r,(o&1?1:-1));
		}
	}
}
int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>k>>A>>B>>C>>X>>Y>>Z,init(3e5);
	slv(fx,A,X),slv(fy,B,Y),slv(fz,C,Z);
	int l=1,r=0;while(l<=k*2)l<<=1,r++;
	for(int i=0;i<l;i++)rev[i]=rev[i>>1]>>1|(i&1)<<r-1;
	for(int i=0;i<=k;i++)fx[i]=fx[i]*inv[i]%mod,fy[i]=fy[i]*inv[i]%mod;
	NTT(fx,l,1),NTT(fy,l,1);
	for(int i=0;i<l;i++)fx[i]=fx[i]*fy[i]%mod;
	NTT(fx,l,0);ll invl=qp(l,mod-2);
	for(int i=0;i<l;i++)fx[i]=fx[i]*invl%mod;
	for(int i=0;i<=k;i++)ans=(ans+fx[i]*fz[k-i]%mod*inv[k-i])%mod;
	cout<<ans*fc[k]%mod<<'\n';
	return 0;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 7ms
memory: 12996kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 5
Accepted
time: 3ms
memory: 13052kb

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: 91ms
memory: 13464kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 10
Accepted
time: 84ms
memory: 13348kb

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: 90ms
memory: 19164kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 15
Accepted
time: 176ms
memory: 19104kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 15
Accepted
time: 50ms
memory: 19104kb

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: 53ms
memory: 19096kb

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: 163ms
memory: 19164kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 15
Accepted
time: 158ms
memory: 19092kb

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: 120ms
memory: 19040kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 35
Accepted
time: 156ms
memory: 19088kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 35
Accepted
time: 176ms
memory: 19160kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 35
Accepted
time: 207ms
memory: 19120kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 35
Accepted
time: 216ms
memory: 19104kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 35
Accepted
time: 251ms
memory: 19044kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 35
Accepted
time: 313ms
memory: 19160kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 35
Accepted
time: 568ms
memory: 19160kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 35
Accepted
time: 364ms
memory: 19036kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 35
Accepted
time: 201ms
memory: 19116kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 35
Accepted
time: 67ms
memory: 19048kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 35
Accepted
time: 62ms
memory: 19164kb

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: 160ms
memory: 19108kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 10
Accepted
time: 204ms
memory: 19108kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 10
Accepted
time: 243ms
memory: 19120kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 10
Accepted
time: 278ms
memory: 19124kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 10
Accepted
time: 327ms
memory: 19164kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 10
Accepted
time: 365ms
memory: 19100kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 10
Accepted
time: 439ms
memory: 19060kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 10
Accepted
time: 845ms
memory: 19108kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 10
Accepted
time: 518ms
memory: 14360kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 10
Accepted
time: 286ms
memory: 14424kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 10
Accepted
time: 98ms
memory: 14420kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

score: 10
Accepted
time: 68ms
memory: 14484kb

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"