QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#400685#4903. 细菌Iratis90 1422ms61376kbC++204.0kb2024-04-27 15:07:162024-04-27 15:07:17

Judging History

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

  • [2024-04-27 15:07:17]
  • 评测
  • 测评结果:90
  • 用时:1422ms
  • 内存:61376kb
  • [2024-04-27 15:07:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define md(a) a=(a%mod+mod)%mod
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)

bool ST;

const int N=1000005,mod=998244353;
namespace Math
{
	int fac[N],inv[N],upd,iv[N];
	inline void add(int &x,const int &y){x+=y;if(x>=mod)x-=mod;}
	inline void dec(int &x,const int &y){x-=y;if(x<0)x+=mod;}
	inline int qp(int a,int n){int b=1;while(n){if(n&1)b=b*a%mod;a=a*a%mod,n>>=1;}return b;}
	inline void PreC()
	{
		upd=N-5,fac[0]=1;for(int i=1;i<=upd;i++)fac[i]=fac[i-1]*i%mod;
		inv[upd]=qp(fac[upd],mod-2);for(int i=upd-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
		for(int i=1;i<=upd;i++)iv[i]=inv[i]*fac[i-1]%mod;
	}
	inline int C(int n,int m){if(n<m||m<0)return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;}
};
using namespace Math;
int Day,n,m,h,qx,qy,qz,X[N],Y[N],Z[N];

namespace Force
{
	int dp[N],tmp[N];int *f;int *g;
	inline void main(int p,int q,int *Val)
	{
		f=dp+n,g=tmp+n;for(int i=-p;i<=q;i++)f[i]=0;f[0]=1;Val[0]=1;
		for(int d=1;d<=Day;d++)
		{
			for(int i=-p;i<=q;i++)g[i]=f[i],f[i]=0;
			for(int i=-p;i<=q;i++){if(i-1>=-p)add(f[i-1],g[i]);if(i+1<=q)add(f[i+1],g[i]);}
			for(int i=-p;i<=q;i++)add(Val[d],f[i]);
		}
	}
};
inline void Rev(int &x,int &y,int p){x+=p,y-=p;swap(x,y);}

namespace Right
{
	int P,Q;
	inline void Push(int &val,int l,int r,int d)
	{
		val=val*2%mod;dec(val,C(d,l)),add(val,C(d,r+1));
		val=val*2%mod;dec(val,C(d+1,r+1)),add(val,C(d+1,l));
	}
	inline void Start(int x,int y,int tag,int *f)
	{
		// cout<<x<<" "<<y<<endl;
		int l,r,val;
		l=ceil((-P)/2.0)-x,r=floor(Q/2.0)-x,val=0;for(int i=0;i<=0;i++)if(l<=i&&i<=r)add(val,C(0,i));
		for(int d=0;d<=Day;d+=2)add(f[d],val*tag%mod),Push(val,l,r,d),l++,r++;
		l=ceil((1-P)/2.0)-x,r=floor((1+Q)/2.0)-x,val=0;for(int i=0;i<=1;i++)if(l<=i&&i<=r)add(val,C(1,i));
		for(int d=1;d<=Day;d+=2)add(f[d],val*tag%mod),Push(val,l,r,d),l++,r++;
	}
	inline void main(int p,int q,int *f)
	{
		P=p,Q=q,p++,q++;int x=0,y=0;Start(x,y,1,f);
		x=y=0;for(int t=1;t<=Day/(p+q)+2;t++){if(t&1)Rev(x,y,p);else Rev(x,y,-q);Start(x,y,(t&1)?mod-1:1,f);}
		x=y=0;for(int t=1;t<=Day/(p+q)+2;t++){if(t&1)Rev(x,y,-q);else Rev(x,y,p);Start(x,y,(t&1)?mod-1:1,f);}
	}
};

namespace Iratis
{
	inline void main(int p,int q,int *Val)
	{
		// Force::main(p,q,Val);return ;
		// Right::main(p,q,Val);return ;
		if(p+q+1<=800)Force::main(p,q,Val);
		else Right::main(p,q,Val);
	}
};

namespace cul8r
{
	int lim,l,A[N],B[N],rev[N],ome[N],va[N],vb[N];
	inline void NTT(int *A,int type)
	{
		for(int i=0;i<lim;i++)if(i<rev[i])swap(A[i],A[rev[i]]);
		for(int p=1;p<=l;p++)
		{
			int m=(1<<p),wm=qp(3,(mod-1)/m);if(type==-1)wm=qp(wm,mod-2);
			ome[0]=1;for(int j=1;j<m/2;j++)ome[j]=1ll*ome[j-1]*wm%mod;
			for(int i=0;i<lim;i+=m)for(int j=0;j<m/2;j++)
			{
				int u=A[i+j],t=1ll*ome[j]*A[i+j+m/2]%mod,v=u-t;u+=t;
				if(u>=mod)u-=mod;if(v<0)v+=mod;A[i+j]=u,A[i+j+m/2]=v;
			}
		}
	}
	inline void Merge(int n,int m)
	{
		lim=1,l=0;while(lim<=n+m)lim<<=1,l++;
		for(int i=0;i<lim;i++)rev[i]=((rev[i>>1]>>1)|((i&1)<<(l-1))),A[i]=B[i]=0;
		for(int i=0;i<=n;i++)A[i]=va[i];for(int i=0;i<=m;i++)B[i]=vb[i];
		NTT(A,1),NTT(B,1);for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;int P=qp(lim,mod-2);
		NTT(A,-1);for(int i=0;i<lim;i++)A[i]=1ll*A[i]*P%mod;for(int i=0;i<=n+m;i++)va[i]=A[i];
	}
	inline void solve()
	{
		// for(int i=0;i<=Day;i++)cerr<<X[i]<<' ';cout<<'\n';
		// for(int i=0;i<=Day;i++)cerr<<Y[i]<<' ';cout<<'\n';
		// for(int i=0;i<=Day;i++)cerr<<Z[i]<<' ';cout<<'\n';
		for(int i=0;i<=Day;i++)va[i]=X[i]*inv[i]%mod,vb[i]=Y[i]*inv[i]%mod;Merge(Day,Day);
		for(int i=0;i<=Day;i++)vb[i]=Z[i]*inv[i]%mod;Merge(Day,Day);cout<<va[Day]*fac[Day]%mod<<'\n';
	}
};

bool ED;

signed main()
{
    int time_st=clock();
	cerr<<(&ST-&ED)/1024.0/1024<<endl;ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>Day>>n>>m>>h>>qx>>qy>>qz;PreC();
	Iratis::main(qx-1,n-qx,X),Iratis::main(qy-1,m-qy,Y),Iratis::main(qz-1,h-qz,Z);
	cul8r::solve();cerr<<(clock()-time_st)/1e6<<endl;return 0;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

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

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 18ms
memory: 46580kb

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: 11ms
memory: 37996kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 8ms
memory: 40880kb

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: 203ms
memory: 58388kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 742ms
memory: 56184kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 69ms
memory: 55316kb

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: 79ms
memory: 53812kb

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

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 163ms
memory: 55952kb

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: 356ms
memory: 61260kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 441ms
memory: 60244kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 555ms
memory: 58240kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 651ms
memory: 61376kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 742ms
memory: 56608kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 843ms
memory: 61144kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 1422ms
memory: 56388kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 747ms
memory: 56512kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 334ms
memory: 54652kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

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

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 95ms
memory: 57944kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 80ms
memory: 57740kb

input:

120000 119996 119994 1 58014 49559 1

output:

682979057

result:

ok 1 number(s): "682979057"

Subtask #7:

score: 0
Time Limit Exceeded

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: 506ms
memory: 56424kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 641ms
memory: 61372kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 810ms
memory: 58800kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 949ms
memory: 57132kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 1088ms
memory: 56464kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 1244ms
memory: 58736kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: -10
Time Limit Exceeded

input:

120000 993 998 991 196 712 911

output:

464727191

result: