QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#400668#4903. 细菌Iratis15 256ms41508kbC++203.6kb2024-04-27 14:53:252024-04-27 14:53:26

Judging History

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

  • [2024-04-27 14:53:26]
  • 评测
  • 测评结果:15
  • 用时:256ms
  • 内存:41508kb
  • [2024-04-27 14:53:25]
  • 提交

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 Start(int x,int y,int tag,int *f)
	{
		for(int d=0;d<=Day;d++)
		{
			int l=ceil((d-P)/2.0),r=floor((d+Q)/2.0),sum=0;l-=x;r-=x;
			for(int i=l;i<=r;i++)add(sum,C(d,i));add(f[d],sum*tag%mod);
		}
	}
	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/n+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/n+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(n<=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: 6ms
memory: 38600kb

input:

50 41 46 42 8 20 21

output:




791406134

result:

ok 1 number(s): "791406134"

Test #2:

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

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: 243ms
memory: 40320kb

input:

5000 4994 4990 4990 976 2257 2505

output:




836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 256ms
memory: 41508kb

input:

5000 4994 4997 4994 4399 1826 1332

output:




65414465

result:

ok 1 number(s): "65414465"

Subtask #3:

score: 0
Time Limit Exceeded

Test #5:

score: 0
Time Limit Exceeded

input:

120000 300 1 1 141 1 1

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #8:

score: 0
Time Limit Exceeded

input:

119000 119991 119991 1 23819 52139 1

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #3:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%