QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#400681#4903. 细菌Iratis55 739ms60716kbC++204.0kb2024-04-27 15:04:562024-04-27 15:04:56

Judging History

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

  • [2024-04-27 15:04:56]
  • 评测
  • 测评结果:55
  • 用时:739ms
  • 内存:60716kb
  • [2024-04-27 15:04:56]
  • 提交

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)+5;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)+5;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<=sqrt(Day))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: 4ms
memory: 39300kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

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

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: 16ms
memory: 38348kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 12ms
memory: 39988kb

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: 211ms
memory: 56592kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

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

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 79ms
memory: 60716kb

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: 86ms
memory: 57944kb

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: 172ms
memory: 54288kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 183ms
memory: 54172kb

input:

120000 13997 13997 1 9768 6131 1

output:

151873213

result:

ok 1 number(s): "151873213"

Subtask #6:

score: 0
Time Limit Exceeded

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Test #11:

score: 35
Accepted
time: 352ms
memory: 58972kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: -35
Time Limit Exceeded

input:

120000 395 390 1 370 185 1

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

0%