QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91869#4903. 细菌SenseAnone100 ✓1013ms15828kbC++143.5kb2023-03-29 19:38:422023-03-29 19:38:45

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-29 19:38:45]
  • 评测
  • 测评结果:100
  • 用时:1013ms
  • 内存:15828kb
  • [2023-03-29 19:38:42]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
const int MOD=998244353,g=3,gi=(MOD+1)/3;
inline int Add(int a,int b){return (a+b)%MOD;}
inline int Dec(int a,int b){return (a-b+MOD)%MOD;}
inline int Mul(int a,int b){return 1ll*a*b%MOD;}
inline int qpow(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1) ret=Mul(ret,a);
		b>>=1;a=Mul(a,a);
	}
	return ret;
}
int d,To[2000005],N,Lg;
void NTT(int *S,int op)
{
	for(int i=0;i<N;i++) if(i<To[i]) swap(S[i],S[To[i]]);
	for(int i=1;i<N;i<<=1)
	{
		int W=qpow(op==1?g:gi,(MOD-1)/(i<<1));
		for(int j=0;j<N;j+=i<<1)
		{
			int w=1;
			for(int k=0;k<i;k++,w=Mul(w,W))
			{
				int x=S[j+k],y=Mul(S[i+j+k],w);
				S[j+k]=Add(x,y); S[i+j+k]=Dec(x,y);
			}
		}
	}
	if(op==-1)
	{
		int Inv=qpow(N,MOD-2);
		for(int i=0;i<N;i++) S[i]=Mul(S[i],Inv);
	}
}
int dp[2][1005];
int Fac[250005],Inv[250005]; 
inline int C(int n,int r){return r>n||r<0?0:Mul(Fac[n],Mul(Inv[r],Inv[n-r]));}
int Solve1(int a,int b,int k1,int k2);
int Solve2(int a,int b,int k1,int k2);
inline int Calc(int X1,int Y1,int X2,int Y2){return (X2-X1+Y2-Y1)&1||Y2-Y1>X2-X1||Y1-Y2>X2-X1?0:C(X2-X1,(X2-X1+Y2-Y1)/2);}
int Solve1(int a,int b,int k1,int k2)//不碰 y=k1 和 y=k2 从原点到 (a,b) 
{
	if(a<-b||a<b) return 0;
	return Dec(Dec(Calc(0,0,a,b),Calc(0,0,a,2*k2-b)),Solve2(a,b,k1,k2));
}
int Solve2(int a,int b,int k1,int k2)//指定碰 y=k1 而不碰 y=k2
{
	if(a<-b||a<b) return 0;
	if(a<2*k1-b||a<b-2*k1) return 0;
	return Add(Solve1(a,2*k1-b,2*k1-k2,k2),Solve2(a,b,2*k1-k2,k2));	
} 
void Solve(int *f,int n,int p)
{
	if(n<=1000)
	{
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++) dp[0][i]=1;
		f[0]=1;
		for(int i=1;i<=d;i++)
		{
			for(int j=1;j<=n;j++)
				dp[i&1][j]=Add(j-1>=1?dp[!(i&1)][j-1]:0,j+1<=n?dp[!(i&1)][j+1]:0);
			f[i]=dp[i&1][p];
		}
		return;
	}
	/*否则问题就是:从 (0,0) 出发向右上或者右下走,不触碰 y=-p 和 y=n-p+1 走d步到达一个点*/
	f[0]=1;
	for(int i=1;i<=d;i++)
	{
		f[i]=Mul(f[i-1],2);
		f[i]=Dec(f[i],Solve1(i-1,-p+1,-p,n-p+1));
		f[i]=Dec(f[i],Solve1(i-1,n-p,-p,n-p+1));
	}
}
int f[524290],gg[524290],h[524290];
int main() {
//	freopen("output.out","w",stdout);
	int n,m,k,a,b,c;
	read(d);read(n);read(m);read(k);read(a);read(b);read(c);
	Fac[0]=1;
	for(int i=1;i<=120000;i++) Fac[i]=Mul(Fac[i-1],i);
	Inv[120000]=qpow(Fac[120000],MOD-2);
	for(int i=120000-1;i>=0;i--) Inv[i]=Mul(Inv[i+1],i+1);
	Solve(f,n,a); Solve(gg,m,b); Solve(h,k,c);
	for(N=1,Lg=0;N<524288;N<<=1,Lg++);
	for(int i=0;i<N;i++) To[i]=(To[i>>1]>>1)|((i&1)<<(Lg-1));
//	for(int i=0;i<=d;i++)
//		printf("(%d,%d,%d)\n",f[i],gg[i],h[i]);
	for(int i=0;i<=d;i++) 
	{
		f[i]=Mul(Inv[i],f[i]);
		gg[i]=Mul(Inv[i],gg[i]);
		h[i]=Mul(Inv[i],h[i]);
	}
	NTT(f,1); NTT(gg,1); NTT(h,1);
	for(int i=0;i<N;i++) f[i]=Mul(f[i],Mul(gg[i],h[i]));
	NTT(f,-1);
	printf("%d",Mul(f[d],Fac[d]));
	return 0;
}
/*
瑶草一何碧,春入武陵溪。溪上桃花无数,花上有黄鹂。我欲穿花寻路,直入白云深处,浩气展虹霓。只恐花深里,红露湿人衣。
坐玉石,欹玉枕。拂金徽。谪仙何处,无人伴我白螺杯。我为灵芝仙草,不为朱唇丹脸,长啸亦何为。醉舞下山去,明月逐人归。
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 131ms
memory: 14964kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 124ms
memory: 13988kb

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: 128ms
memory: 14432kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 126ms
memory: 14204kb

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: 212ms
memory: 14160kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 416ms
memory: 15756kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 133ms
memory: 14292kb

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: 128ms
memory: 14528kb

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: 156ms
memory: 15404kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 155ms
memory: 15464kb

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: 299ms
memory: 14564kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

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

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 431ms
memory: 14860kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 463ms
memory: 15408kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 528ms
memory: 14504kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 588ms
memory: 14776kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

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

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

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

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 197ms
memory: 14644kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 171ms
memory: 15512kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 142ms
memory: 13916kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 128ms
memory: 14780kb

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: 387ms
memory: 13888kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 469ms
memory: 13832kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 558ms
memory: 15024kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 638ms
memory: 15584kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

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

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 831ms
memory: 14236kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 1013ms
memory: 14736kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 429ms
memory: 15828kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 245ms
memory: 15280kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 182ms
memory: 14344kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 139ms
memory: 14424kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

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

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"