QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#295886#4903. 细菌ucup-team1004100 ✓1235ms14160kbC++143.6kb2024-01-01 13:51:042024-01-01 13:51:05

Judging History

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

  • [2024-01-01 13:51:05]
  • 评测
  • 测评结果:100
  • 用时:1235ms
  • 内存:14160kb
  • [2024-01-01 13:51:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) (a).begin(),(a).end()
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
	out<<'[';
	for(T x:a)out<<x<<',';
	return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
	cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
	cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int mod=998244353;
ll qpow(ll x,ll y=mod-2,ll ans=1){
	for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
	return ans;
}
namespace Poly{
	const int N=1<<18,g=3;
	int lim,rev[N],A[N],B[N],pw[N];
	void init(int n){
		for(lim=1;lim<n;lim<<=1);
		for(int i=1;i<lim;i++)rev[i]=rev[i>>1]>>1|(i&1?lim>>1:0);
	}
	void Init(){
		int x=qpow(g,(mod-1)/N);
		pw[N/2]=1;
		for(int i=N/2+1;i<N;i++)pw[i]=1ll*pw[i-1]*x%mod;
		for(int i=N/2-1;i;i--)pw[i]=pw[i<<1];
	}
	namespace Public{
		using poly=vector<int>;
		void NTT(int *f,int op){
			static unsigned long long a[N];
			for(int i=0;i<lim;i++)a[i]=f[rev[i]];
			for(int len=1,x;len<lim;len<<=1){
				for(int i=0;i<lim;i+=len<<1){
					for(int j=0;j<len;j++){
						x=a[i|j|len]*pw[len|j]%mod;
						a[i|j|len]=a[i|j]+mod-x,a[i|j]+=x;
					}
				}
			}
			for(int i=0;i<lim;i++)f[i]=a[i]%mod;
			if(op<0){
				reverse(f+1,f+lim);
				int x=qpow(lim);
				for(int i=0;i<lim;i++)f[i]=1ll*f[i]*x%mod;
			}
		}
		poly operator * (const poly &a,const poly &b){
			int n=a.size(),m=b.size(),k=n+m-1;
			init(k);
			copy(a.begin(),a.end(),A),fill(A+n,A+lim,0);
			copy(b.begin(),b.end(),B),fill(B+m,B+lim,0);
			poly c(k);
			NTT(A,1),NTT(B,1);
			for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
			NTT(A,-1);
			for(int i=0;i<k;i++)c[i]=A[i];
			return c;
		}
		poly& operator %= (poly &a,const int &b){
			if(a.size()>b)a.resize(b);
			return a;
		}
		poly operator % (const poly &a,const int &b){
			poly c(a);
			return c%=b;
		}
	}
}
using namespace Poly::Public;
const int N=1.2e5+10;
int d,n,m,k,a,b,c;
int fac[N],ifac[N];
void init(int n=d){
	for(int i=fac[0]=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n]=qpow(fac[n]);
	for(int i=n;i>=1;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
}
int C(int n,int m){
	if(0>m||m>n)return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
const int B=501;
poly gen1(int n,int x){
	static int f[2][B];
	int now=1,las=0;
	memset(f,0,sizeof f);
	f[now][x]=1;
	poly g(d+1);
	for(int i=0;i<=d;i++){
		g[i]=accumulate(f[now]+1,f[now]+1+n,0ll)%mod;
		swap(now,las);
		for(int j=1;j<=n;j++)f[now][j]=(f[las][j-1]+f[las][j+1])%mod;
	}
	// debug(n,x,g);
	return g;
}
poly gen2(int a,int b){
	int n=a+b;
	poly f(d+1);
	vector<tuple<int,int,int,int>>s;
	for(int l=-a,r=b,w=1;r>=-d;l-=n,r-=n,w=-w)s.push_back({l,r,w,0});
	for(int l=-a,r=b,w=1;l+=n,r+=n,w=-w,l<=d;)s.push_back({l,r,w,0});
	for(auto &[l,r,w,t]:s)t=l<=0&&0<=r;
	f[0]=1;
	for(int i=1;i<=d;i++){
		for(auto &[l,r,w,t]:s){
			t=t*2%mod;
			if((r&1)^(i&1))(t+=C(i-1,(-r+i-1)/2))%=mod;
			else (t+=mod-C(i-1,(-r+i)/2))%=mod;
			if((l&1)^(i&1))(t+=C(i-1,(-l+i-1)/2))%=mod;
			else (t+=mod-C(i-1,(-l+i)/2-1))%=mod;
			// debug(i,l,r,w,t,(r&1)^(i&1),(l&1)^(i&1));
			f[i]=(f[i]+t*w)%mod;
		}
		f[i]=(f[i]+mod)%mod;
	}
	// debug(a,b,f);
	// exit(0);
	return f;
}
poly gen(int n,int x){
	auto f=n<B?gen1(n,x):gen2(x,n-x+1);
	for(int i=0;i<f.size();i++)f[i]=1ll*f[i]*ifac[i]%mod;
	return f;
}
int main(){
	cin>>d>>n>>m>>k>>a>>b>>c;
	Poly::Init(),init();
	poly f=gen(n,a)*gen(m,b)%(d+1)*gen(k,c);
	f.resize(d+1);
	cout<<1ll*f[d]*fac[d]%mod<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 8284kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 0ms
memory: 7676kb

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: 3ms
memory: 7980kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 3ms
memory: 8624kb

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: 67ms
memory: 14160kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 269ms
memory: 14076kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

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

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

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: 69ms
memory: 14132kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 70ms
memory: 13980kb

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: 104ms
memory: 14096kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 125ms
memory: 14092kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 152ms
memory: 14096kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 850ms
memory: 14076kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 724ms
memory: 14036kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 634ms
memory: 13976kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 509ms
memory: 14044kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 282ms
memory: 14136kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

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

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 82ms
memory: 13948kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

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

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 38ms
memory: 14068kb

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: 140ms
memory: 14068kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 171ms
memory: 13976kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 207ms
memory: 14080kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 1235ms
memory: 14040kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 1052ms
memory: 14136kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 922ms
memory: 13984kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 753ms
memory: 14076kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 398ms
memory: 14068kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 176ms
memory: 14096kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 108ms
memory: 14136kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

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

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

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

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"