QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87580#4903. 细菌H_zwei100 ✓801ms33364kbC++147.9kb2023-03-13 19:47:592023-03-13 19:48:01

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 19:48:01]
  • 评测
  • 测评结果:100
  • 用时:801ms
  • 内存:33364kb
  • [2023-03-13 19:47:59]
  • 提交

answer

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC target("avx,avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("Ofast,fast-math")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#include<iostream>
//#include<string>
//#include<cmath>
//#include<cstdio>
//#include<cctype>
//#include<cstring>
//#include<iomanip>
//#include<cstdlib>
//#include<ctime>
//#include<set>
//#include<map>
//#include<utility>
//#include<queue>
//#include<vector>
//#include<stack>
//#include<sstream>
//#include<algorithm>
using namespace std;
/*=====================================================================*/
#define ll long long
#define int ll
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pdd pair<double,double>
#define ull unsigned long long
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(s) (s).begin(),(s).end()
#define repd(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define forr(i,a,b,c) for(int i=(int)(a);i<=(int)(b);i+=(int)(c))
#define forn(i,p,n) for(int i=(int)(p);i<=(int)(n);++i)
#define ford(i,p,n) for(int i=(int)(n);i>=(int)(p);--i)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();++i)
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define Endl(x) cout<<x<<endl;
#define Blank(x) cout<<x<<" ";
#define modcg(x) if(x>=mod)x-=mod;
#define modcl(x) if(x<0)x+=mod;
#define lowbit(x) x&(-x)
/*=====================================================================*/
string int_to_string(ll n)
{
	string s="";
	while(n)
	{
		ll now=n%10;
		s+=now+'0';
		n/=10;
	}
	reverse(s.begin(),s.end());
	return s;
}
ll string_to_int(string s)
{
	ll n=0;
	rep(i,s.size())
	{
		n*=10;
		n+=s[i]-'0';
	}
	return n;
}
mt19937 GeN(chrono::system_clock::now().time_since_epoch().count());
int Rand(int l,int r)
{
	uniform_int_distribution<>RAND1(l,r);
	return RAND1(GeN);
}
/*======================================================================*/
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
const int month[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};
//think twice,code once
//think once,debug forever
const int MAXN=480020;
const int mod=998244353,gen=3,igen=332748118;
int quickpower(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
		{
			res*=a;
			res%=mod;
		}
		a*=a;
		a%=mod;
		b>>=1;
	}
	return res;
}
int inv(int x)
{
	return quickpower(x,mod-2);
}
struct Poly
{
	int r[MAXN];
	int limit,l,invl;
	void init(int n)
	{
		l=0;
		limit=1;
		while(limit<n)
		{
			limit<<=1;
			l++; 
		}
		invl=::inv(limit);
		rep(i,limit)
		{
			r[i]=(r[i>>1]>>1ll)|((i&1ll)<<(l-1));
		}
	}
	void NTT(vi &a,bool type)
	{
		a.resize(limit);
		rep(i,limit) 
		{
			if(i<r[i])
			{
				swap(a[i],a[r[i]]);
			}
		}
		for(int i=2;;i<<=1)
		{
			if(i>limit)
			{
				break;
			}
			int Gen=quickpower(((type==1)?gen:igen),(mod-1)/i);
			forr(j,0,limit-1,i)
			{
				int w=1;
				forn(k,j,(i>>1)+j-1)
				{
					int cur=w*a[k+(i>>1)]%mod;
					a[k+(i>>1)]=((a[k]-cur)%mod+mod)%mod;
					a[k]=(a[k]+cur)%mod;
					w*=Gen;
					w%=mod;
				}
			}
		}
	}
	vi mul(vi f,vi g)
	{
		int n=f.size();
		int m=g.size();	
		init(n+m);
		NTT(f,1);
		NTT(g,1);
		rep(i,limit)
		{
			f[i]=f[i]*g[i]%mod*invl%mod;
		}
		NTT(f,0);
		f.resize(n+m);
		return f;
	}
	vi inv(vi f)
	{
		if(f.size()==1)
		{
			f[0]=::inv(f[0]);
			return f;
		}
		int all=f.size();
		vi nf=f;
		nf.resize((all+1)/2);	
		nf=inv(nf);
		vi nf1=nf;
		nf1=mul(nf1,f);
		nf1.resize(all);
		rep(i,nf1.size())
		{
			nf1[i]=-nf1[i];
			modcl(nf1[i]);
		}
		nf1[0]+=2;
		modcg(nf1[0]);
		f=mul(nf,nf1);
		f.resize(all);
		return f;
	}
}P;
struct combination
{
	int F[MAXN],invF[MAXN];
	int P[MAXN];
	void init(int n)
	{
		F[0]=1;
		P[0]=1;
		forn(i,1,n)
		{
			F[i]=(F[i-1]*i)%mod;
			P[i]=P[i-1]+P[i-1];
			modcg(P[i]);
		}
		invF[n]=inv(F[n]);
		ford(i,0,n-1)
		{
			invF[i]=(invF[i+1]*(i+1))%mod;
		}
	}
	int C(int n,int m)
	{
		if(n<0||m<0||n<m)
		{
			return 0;
		}
		return ((F[n]*invF[m])%mod*invF[n-m])%mod;
	}
	int A(int n,int m)
	{
		if(n<0||m<0||n<m)
		{
			return 0;
		}
		return F[n]*invF[n-m]%mod;
	}
}C;
int n[3];
int x[3];
int d;
vi ans[3];
void doit(int id)
{
	vi S,A;
	S.resize(d+1);
	A.resize(d+1);
	int a=x[id],b=n[id]+1-x[id];
	forn(i,1,d)
	{
		if((i-a>=0)&&(!((i-a)&1)))
		{
			S[i]+=C.C(i,(i-a)>>1);
			modcg(S[i]);
		}
		if((i-b>=0)&&(!((i-b)&1)))
		{
			S[i]+=C.C(i,(i-b)>>1);
			modcg(S[i]);
		}
		if(!(i&1))
		{
			A[i]+=C.C(i,i>>1);
			modcg(A[i]);
		}
		if((i-n[id]-1>=0)&&(!((i-n[id]-1)&1)))
		{
			A[i]+=C.C(i,(i-n[id]-1)>>1);
			modcg(A[i]);
		}
	}
	A[0]=1;
//	S[0]=0;
//	for(int u:A)
//	{
//		cout<<u<<" ";
//	}
//	cout<<endl;
//	for(int u:S)
//	{
//		cout<<u<<" ";
//	}
//	cout<<endl;
	A=P.inv(A);
	ans[id]=P.mul(A,S);
	ans[id].resize(d+1);
//	for(int u:ans[id])
//	{
//		cout<<u<<" ";
//	}
//	cout<<endl; 
	ans[id][0]=C.P[0];
	forn(i,1,d)
	{
		ans[id][i]=-ans[id][i];
		modcl(ans[id][i]);
		ans[id][i]+=ans[id][i-1];
		modcg(ans[id][i]);
		ans[id][i]+=ans[id][i-1];
		modcg(ans[id][i]);
	}
	forn(i,0,d)
	{
		ans[id][i]*=C.invF[i];
		ans[id][i]%=mod;
//		cout<<ans[id][i]<<" ";
	}
//	cout<<endl;
}
void solve()
{
	cin>>d;
	rep(i,3)
	{
		cin>>n[i];	
	}
	rep(i,3)
	{
		cin>>x[i];
	}
	C.init(d);
	rep(i,3)
	{
		doit(i);
	}
//	rep(i,3)
//	{
//		for(int u:ans[i])
//		{
//			cout<<u<<" ";
//		}
//		cout<<endl;
//	}
	ans[0]=P.mul(ans[0],ans[1]);
	ans[0].resize(d+1);
	ans[0]=P.mul(ans[0],ans[2]);
	int ANS=ans[0][d]*C.F[d]%mod;
	cout<<ANS<<endl;
}
/*======================================================================*/
signed main()
{
    cin.tie(0);
    cout.tie(0);
	std::ios::sync_with_stdio(false);
//#define Hank2007
#ifdef Hank2007
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
  	/*====================================================================*/
  	int TEST_CASE=1;
//	cin>>TEST_CASE;
  	while(TEST_CASE--)
  	{
  		solve();
  	}
  	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: 7524kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 2ms
memory: 7544kb

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: 18ms
memory: 8072kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 19ms
memory: 8128kb

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: 716ms
memory: 31416kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 719ms
memory: 31456kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 709ms
memory: 28492kb

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: 725ms
memory: 31624kb

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

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 731ms
memory: 29052kb

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: 724ms
memory: 33212kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 717ms
memory: 32040kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 713ms
memory: 28444kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 744ms
memory: 31244kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 751ms
memory: 29148kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 746ms
memory: 27028kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

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

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 737ms
memory: 33364kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 726ms
memory: 29292kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 726ms
memory: 26652kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 728ms
memory: 26544kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 731ms
memory: 28480kb

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: 714ms
memory: 26512kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 736ms
memory: 28972kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 730ms
memory: 26924kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 738ms
memory: 31380kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 739ms
memory: 31368kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 702ms
memory: 28408kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 721ms
memory: 31388kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 714ms
memory: 33216kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 711ms
memory: 31604kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 706ms
memory: 29836kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 801ms
memory: 28472kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

score: 0
Accepted
time: 735ms
memory: 31352kb

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"