QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#400700#4903. 细菌wdnmdwrnmmp100 ✓547ms19340kbC++143.6kb2024-04-27 15:15:542024-04-27 15:15:56

Judging History

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

  • [2024-04-27 15:15:56]
  • 评测
  • 测评结果:100
  • 用时:547ms
  • 内存:19340kb
  • [2024-04-27 15:15:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

const int N=1<<18, mod=998244353;
int md(const int &x){
	return x>=mod? x-mod: x;
}
int qpow(int x,int y){
	int res=1;
	while(y){
		if(y%2) res=res*x%mod;
		x=x*x%mod;
		y/=2;
	}
	return res;
}int inv(int x){return qpow(x,mod-2);}
int fac[N],ifac[N],P[N];
void init(){
	fac[0]=1;
	rep(i,1,N-1){
		fac[i]=fac[i-1]*i%mod;
	}
	ifac[N-1]=inv(fac[N-1]);
	per(i,N-1,1){
		ifac[i-1]=ifac[i]*i%mod;
	}
	rep(i,0,17){
		int stp=qpow(3,(mod-1)>>(i+1));
		P[1<<i]=1;
		rep(j,(1<<i)+1,(2<<i)-1){
			P[j]=P[j-1]*stp%mod;
		}
	}
}
int C(int m,int n){
	return n<0 || n>m? 0: fac[m]*ifac[n]%mod*ifac[m-n]%mod;
}
int Sum(int n,int l,int r){
	l=max(0ll, l), r=min(n, r);
	int res=0;
	rep(i,l,r){
		res+= C(n,i);
	}
	return res%mod;
}
void DIF(vi &a){
	per(i,17,0){
		int len=1<<i;
		for(int j=0;j<N;j+=len*2){
			int idx=len;
			rep(k,j,j+len-1){
				int A=a[k], B=a[k+len];
				a[k]=md(A+B), a[k+len]=(A-B+mod)*P[idx++]%mod;
			}
		}
	}
}
void DIT(vi &a){
	rep(i,0,17){
		int len=1<<i;
		for(int j=0;j<N;j+=len*2){
			int idx=len;
			rep(k,j,j+len-1){
				int A=a[k], B=a[k+len]*P[idx++]%mod;
				a[k]=md(A+B), a[k+len]=md(A-B+mod);
			}
		}
	}
	reverse(a.begin()+1,a.end());
	int iv=inv(N);
	for(int &x:a){
		(x*= iv )%=mod;
	}
}
vi mul(vi x,vi y){
	x.resize(N), y.resize(N);
	DIF(x); DIF(y);
	rep(i,0,N-1){
		(x[i]*= y[i] )%=mod;
	}
	DIT(x);
	return x;
}
vi solve(int n,int a,int d){
	if(n==1){
		vi res(d+1,0);
		res[0]=1;
		return res;
	}
	if(n<=1500){
		vi f(n,1),res(d+1,0);
		res[0]=1;
		rep(i,1,d){
			vi tmp(n);
			tmp[0]=f[1], tmp[n-1]=f[n-2];
			rep(j,1,n-2){
				tmp[j]=md(f[j-1]+f[j+1]);
			}
			swap(f,tmp);
			res[i]=f[a]*ifac[i]%mod;
		}
		return res;
	}
	else{
		vi res(d+1,0);
		auto calc=[&](int cx,int op){
			{
				int cle=cx&1, cri=(cx+n)%2? n-1: n-2;
				int dn=0, dl=(cle-cx)/2, dr=(cri-cx)/2;
				int csum=Sum(0, dl, dr);
				res[0]+=op*csum;
				for(int i=2;i<=d;i+=2){
					csum=(csum*2-C(dn,dl)+C(dn,dr+1))%mod;
					dn++, dl++, dr++;
					csum=(csum*2+C(dn,dl-1)-C(dn,dr))%mod;
					dn++;
					res[i]+=op*csum;
				}
			}
			{
				int cle=(cx+1)&1, cri=(cx+1+n)%2? n-1: n-2;
				int dn=1, dl=(cle-cx+1)/2, dr=(cri-cx+1)/2;
				int csum=Sum(1, dl, dr);
				res[1]+=op*csum;
				for(int i=3;i<=d;i+=2){
					csum=(csum*2-C(dn,dl)+C(dn,dr+1))%mod;
					dn++, dl++, dr++;
					csum=(csum*2+C(dn,dl-1)-C(dn,dr))%mod;
					dn++;
					res[i]+=op*csum;
				}
			}
		};
		calc(a,1);
		int cx=a,op=1;
		while(1){
			if(op==1){
				cx=-2-cx, op=-1;
			}
			else{
				cx=n*2-cx, op=1;
			}
			if(abs(cx)>d && abs(cx-(n-1))>d){
				break;
			}
			calc(cx,op);
		}
		cx=a, op=1;
		while(1){
			if(op==1){
				cx=n*2-cx, op=-1;
			}
			else{
				cx=-2-cx, op=1;
			}
			if(abs(cx)>d && abs(cx-(n-1))>d){
				break;
			}
			calc(cx,op);
		}
		rep(i,0,d){
			res[i]=(res[i]%mod+mod)*ifac[i]%mod;
		}
		return res;
	}
}
int d,n,m,k,a,b,c;
signed main(){
	// freopen("bacteria.in","r",stdin);
	// freopen("bacteria.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	init();
	cin>>d>>n>>m>>k>>a>>b>>c;
	solve(n,a-1,d);
	vi X=solve(n,a-1,d), Y=solve(m,b-1,d), Z=solve(k,c-1,d);
	X=mul(X,Y);
	X.resize(d+1);
	X=mul(X,Z);
	X.resize(d+1);
	int ans=X[d]*fac[d]%mod;
	cout<<ans<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 32ms
memory: 15388kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 36ms
memory: 15516kb

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: 33ms
memory: 15672kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 36ms
memory: 15652kb

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: 89ms
memory: 19112kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 200ms
memory: 19136kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 41ms
memory: 19112kb

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: 48ms
memory: 19176kb

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

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 96ms
memory: 19204kb

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: 119ms
memory: 19268kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 140ms
memory: 19128kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 170ms
memory: 19104kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 184ms
memory: 19104kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 211ms
memory: 19108kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 224ms
memory: 19140kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 287ms
memory: 19332kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 421ms
memory: 19296kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 193ms
memory: 19148kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 114ms
memory: 19128kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 48ms
memory: 19148kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 39ms
memory: 19128kb

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: 141ms
memory: 19340kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 169ms
memory: 19132kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 212ms
memory: 19116kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 247ms
memory: 19284kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 276ms
memory: 19288kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 306ms
memory: 19196kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

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

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 547ms
memory: 19328kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 240ms
memory: 19148kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 144ms
memory: 19124kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 47ms
memory: 19280kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

score: 0
Accepted
time: 50ms
memory: 19144kb

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"