QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91891#4903. 细菌OtoriEmu100 ✓869ms26336kbC++143.7kb2023-03-29 20:14:162023-03-29 20:14:17

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 20:14:17]
  • 评测
  • 测评结果:100
  • 用时:869ms
  • 内存:26336kb
  • [2023-03-29 20:14:16]
  • 提交

answer

/*
¤ï¤ó¤ï¤ó¡­¡­¤ï¤ó¤À¤Û©`¤¤¤Ã¡î
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
int read()
{
	int x=0;
	char c=getchar();
	while(c<'0' || c>'9')	c=getchar();
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x;
}
void write(int x)
{
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
typedef pair<int,int> P;
typedef vector<int> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define len(x) (int(x.size()))
#define inlp(x,y) putchar(x==y?'\n':' ')
const int MOD=998244353,GG=3,Gi=(MOD+1)/GG;
inline int Add(int u,int v){return u+v>=MOD?u+v-MOD:u+v;}
inline int Sub(int u,int v){return u-v>=0?u-v:u-v+MOD;}
inline int Mul(int u,int v){return LL(u)*LL(v)%MOD;}
inline int add(int &u,int v){return u=Add(u,v);}
inline int sub(int &u,int v){return u=Sub(u,v);}
inline int mul(int &u,int v){return u=Mul(u,v);}
int QuickPow(int x,int p=MOD-2)
{
	int ans=1,base=x;
	while(p)
	{
		if(p&1)	mul(ans,base);
		mul(base,base);
		p>>=1;
	}
	return ans;
}
int fac[1000005],ifac[1000005];
inline int C(int n,int m){return n<m || m<0?0:Mul(fac[n],Mul(ifac[m],ifac[n-m]));}
int rev[1000005],lim;
void makeRev(){for(int i=0;i<lim;++i)	rev[i]=(rev[i>>1]>>1)|((i&1)?(lim>>1):0);}
void NTT(Poly &r,int flag)
{
	for(int i=0;i<lim;++i)	if(i<rev[i])	swap(r[i],r[rev[i]]);
	for(int o=2;o<=lim;o<<=1)
	{
		int w=QuickPow(flag==1?GG:Gi,(MOD-1)/o);
		int k=o>>1;
		for(int i=0;i<lim;i+=o)
		{
			int cn=1;
			for(int j=0;j<k;++j)
			{
				int &f=r[i+j],&g=r[i+j+k];
				int dif=Mul(g,cn);
				g=Sub(f,dif),f=Add(f,dif);
				mul(cn,w);
			}
		}
	}
	if(flag==-1)
	{
		int inv=QuickPow(lim);
		for(int i=0;i<lim;++i)	mul(r[i],inv);
	}
}
Poly operator * (Poly f,Poly g)
{
	int d=len(f)+len(g)-1;
	Poly ret;
	lim=1;
	while(lim<d)	lim<<=1;
	makeRev();
	ret.reserve(lim);
	f.resize(lim),g.resize(lim);
	NTT(f,1),NTT(g,1);
	for(int i=0;i<lim;++i)	ret.push_back(Mul(f[i],g[i]));
	NTT(ret,-1);
	ret.resize(d);
	return ret;
}
inline int Abs(int x){return x<0?-x:x;}
inline int calc(int x,int y){return ((x+y)&1)?0:C(x,(x+y)>>1);}
inline int calcf(int x,int y);
inline int calcg(int x,int y);
int k1,k2;
inline int calcf(int x,int y)
{
	if(x<Abs(k1)+Abs(y-k1))	return 0;
	return Sub(calc(x,y),calcg(x,2*k2-y));
}
inline int calcg(int x,int y)
{
	if(x<Abs(k2)+Abs(y-k2))	return 0;
	return Sub(calc(x,y),calcf(x,2*k1-y));
}
int solve(int x,int y,int K1,int K2)
{
	k1=K1,k2=K2;
	return Sub(calc(x,y),Add(calcf(x,2*k1-y),calcg(x,2*k2-y)));
}
int d;
void solve(Poly &F,int p,int c)
{
	F.reserve(d+1);
	if(c<=400)
	{
		static int f[405],g[405];
		for(int i=0;i<=c;++i)	f[i]=g[i]=0;
		F.push_back(1);
		f[p]=1;
		for(int i=1;i<=d;++i)
		{
			for(int j=0;j<=c;++j)
			{
				if(j-1>=0)	add(g[j-1],f[j]);
				if(j+1<=c)	add(g[j+1],f[j]);
			}
			int s=0;
			for(int j=0;j<=c;++j)	add(s,f[j]=g[j]),g[j]=0;
			F.push_back(s);
		}
		return ;
	}
	F.push_back(1);
	for(int i=1;i<=d;++i)
	{
		int x=solve(i-1,-p,-1-p,c+1-p),y=solve(i-1,c-p,-1-p,c+1-p);
		F.push_back(Sub(Add(F.back(),F.back()),Add(x,y)));
	}
}
int n,m,k,a,b,c;
int main(){
	fac[0]=1;
	for(int i=1;i<=1000000;++i)	fac[i]=Mul(fac[i-1],i);
	ifac[1000000]=QuickPow(fac[1000000]);
	for(int i=999999;~i;--i)	ifac[i]=Mul(ifac[i+1],i+1);
	d=read(),n=read()-1,m=read()-1,k=read()-1,a=read()-1,b=read()-1,c=read()-1;
	Poly f,g,h;
	solve(f,a,n),solve(g,b,m),solve(h,c,k);
	for(int i=0;i<=d;++i)	mul(f[i],ifac[i]),mul(g[i],ifac[i]),mul(h[i],ifac[i]);
	f=f*g*h;
	write(Mul(f[d],fac[d])),etr;
	return 0;
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 13ms
memory: 13728kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

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

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

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 17ms
memory: 11936kb

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: 223ms
memory: 25428kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 247ms
memory: 25944kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

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

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: 133ms
memory: 24792kb

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: 139ms
memory: 25692kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

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

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: 287ms
memory: 25240kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 351ms
memory: 24436kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 611ms
memory: 26228kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 531ms
memory: 25760kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 479ms
memory: 26240kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 425ms
memory: 26336kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 362ms
memory: 25804kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 240ms
memory: 25452kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 181ms
memory: 24696kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 154ms
memory: 25508kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 141ms
memory: 26336kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

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

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: 371ms
memory: 24608kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 450ms
memory: 26292kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 869ms
memory: 25600kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 728ms
memory: 26048kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

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

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 562ms
memory: 24636kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 479ms
memory: 26268kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 293ms
memory: 24616kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 202ms
memory: 24288kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 161ms
memory: 26116kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 127ms
memory: 25524kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

score: 0
Accepted
time: 137ms
memory: 24864kb

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"