QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91117#4903. 细菌wyzwyz100 ✓749ms14452kbC++143.1kb2023-03-27 13:02:132023-03-27 13:02:14

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-27 13:02:14]
  • 评测
  • 测评结果:100
  • 用时:749ms
  • 内存:14452kb
  • [2023-03-27 13:02:13]
  • 提交

answer

#include<cstdio>
#include<cctype>
#include<cmath>

#define maxn 303303

const int G=3,mod=998244353;

template<class T>

inline T read(){
	T r=0,f=0;
	char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r*10)+(c^48),c=getchar();
	return f?-r:r;
}

template<class T>

inline T abs(T a){
	return a<0?-a:a;
}

template<class T>

inline T min(T a,T b){
	return a<b?a:b;
}

inline long long qpow(long long a,int b){
	long long ans=1;
	for(;b;b>>=1){
		if(b&1)(ans*=a)%=mod;
		(a*=a)%=mod;
	}
	return ans;
}

unsigned long long A[maxn];

namespace Polyn{

	const int N=262144;

	int rev[maxn];

	long long g[maxn];

	inline void init(){
		for(int i=1;i<N;i++)
			rev[i]=(rev[i>>1]>>1)|(i&1?N>>1:0);
		for(int i=1,p;i<N;i<<=1){
			g[i]=1,p=i<<1;
			long long x=qpow(G,(mod-1)/p);
			for(int j=i+1;j<p;j++)
				g[j]=g[j-1]*x%mod;
		}
	}

	inline void NTT(long long *f,int opt){
		for(int i=0;i<N;i++)
			A[i]=f[rev[i]];
		for(int i=1;i<N;i<<=1)
			for(int j=0,p=i<<1;j<N;j+=p)
				for(int k=0;k<i;k++){
					int l=j|k,r=i|l;
					int val=A[r]*g[i|k]%mod;
					A[r]=A[l]+mod-val,A[l]+=val;
				}
		if(!opt){
			for(int i=0;i<N;i++)
				f[i]=A[i]%mod;
			return;
		}
		int invn=mod-(mod-1)/N;
		f[0]=A[0]%mod*invn%mod;
		for(int i=1;i<N;i++)
			f[i]=A[N-i]%mod*invn%mod;
	}

}

int T,n,m,K,X,Y,Z;

long long pw[maxn],frac[maxn],invf[maxn];

inline void init(int n){
	pw[0]=1,frac[0]=1;
	for(int i=1;i<=n;i++){
		pw[i]=pw[i-1]*2%mod;
		frac[i]=frac[i-1]*i%mod;
	}
	invf[n]=qpow(frac[n],mod-2);
	for(int i=n;i;i--)
		invf[i-1]=invf[i]*i%mod;
}

inline long long C(int n,int m){
	return frac[n]*invf[m]%mod*invf[n-m]%mod;
}

inline long long F(int n,int d){
	if(d>n||(abs(n-d)&1))return 0;
	return C(n,(n-d)/2);
}

long long f[maxn],g[maxn],h[maxn];

inline long long Calc(int n,int N,int X,int pos){
	long long ans=F(n,abs(X-pos));
	long long x=X;
	for(int o=0;;o=!o){//A...
		if(!o)x=-x;
		else x=2*(N+1)-x;
		if(abs(x-pos)>n)break;
		ans+=(o?1:-1)*F(n,abs(x-pos));
	}
	x=X;
	for(int o=1;;o=!o){//A...
		if(!o)x=-x;
		else x=2*(N+1)-x;
		if(abs(x-pos)>n)break;
		ans+=(o?-1:1)*F(n,abs(x-pos));
	}
	return (ans%mod+mod)%mod;
}

inline void calc(int N,int X,long long *f){
    if(N==1)return f[0]=1,void();
	if(N<=sqrt(T)){
		static long long g[maxn],h[maxn];
		for(int i=1;i<=N;i++)g[i]=0;
		g[X]=1;
		for(int t=0;t<=T;t++){
			long long sum=0;
			for(int i=1;i<=N;i++)
				sum+=g[i],h[i-1]+=g[i],h[i+1]+=g[i];
			f[t]=sum%mod*invf[t]%mod,h[0]=h[N+1]=0;
			for(int i=1;i<=N;i++)g[i]=h[i]%mod,h[i]=0;
		}
		return;
	}
	f[0]=1;
	for(int t=1;t<=T;t++)
		f[t]=(f[t-1]*2+2*mod-Calc(t-1,N,X,1)-Calc(t-1,N,X,N))%mod;
	for(int t=1;t<=T;t++)(f[t]*=invf[t])%=mod;
}

int main(){
	init(T=read<int>());
	n=read<int>(),m=read<int>(),K=read<int>();
	X=read<int>(),Y=read<int>(),Z=read<int>();
	calc(n,X,f),calc(m,Y,g),calc(K,Z,h);
	Polyn::init();
	Polyn::NTT(f,0),Polyn::NTT(g,0);
	for(int i=0;i<Polyn::N;i++)(f[i]*=g[i])%=mod;
	Polyn::NTT(f,1);
	long long ans=0;
	for(int i=0;i<=T;i++)
		(ans+=f[i]*h[T-i])%=mod;
	printf("%lld\n",ans*frac[T]%mod);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 24ms
memory: 10708kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 24ms
memory: 10680kb

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: 10784kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

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

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: 73ms
memory: 13528kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 110ms
memory: 13480kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 20ms
memory: 13440kb

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: 31ms
memory: 13488kb

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: 35ms
memory: 13516kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 32ms
memory: 13564kb

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: 111ms
memory: 13468kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 497ms
memory: 13492kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 407ms
memory: 13456kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 369ms
memory: 13492kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 299ms
memory: 13432kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 264ms
memory: 13512kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 260ms
memory: 13468kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 117ms
memory: 13508kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 65ms
memory: 13472kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 42ms
memory: 13560kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 34ms
memory: 13412kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

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

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: 162ms
memory: 14408kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 749ms
memory: 14452kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 592ms
memory: 14364kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 513ms
memory: 14388kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 445ms
memory: 14348kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 370ms
memory: 14396kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 299ms
memory: 14404kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 166ms
memory: 14376kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

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

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 46ms
memory: 14440kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 32ms
memory: 14380kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

score: 0
Accepted
time: 36ms
memory: 14428kb

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"