QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75573#4903. 细菌4182_543_731100 ✓1413ms21080kbC++2.7kb2023-02-05 20:40:542023-02-05 20:40:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 20:40:56]
  • 评测
  • 测评结果:100
  • 用时:1413ms
  • 内存:21080kb
  • [2023-02-05 20:40:54]
  • 提交

answer

#include<cstdio>
#include<vector>
using namespace std;
#define N 263001
#define mod 998244353
int n,l1,l2,l3,s1,s2,s3;
int pw(int a,int p){int as=1;while(p){if(p&1)as=1ll*as*a%mod;a=1ll*a*a%mod;p>>=1;}return as;}
int fr[N],ifr[N],gr[2][N*2],rev[N*2];
void init(int l=18)
{
	fr[0]=1;for(int i=1;i<=1<<l;i++)fr[i]=1ll*i*fr[i-1]%mod;
	ifr[1<<l]=pw(fr[1<<l],mod-2);for(int i=1<<l;i>=1;i--)ifr[i-1]=1ll*i*ifr[i]%mod;
	for(int s=2;s<=1<<l;s<<=1)for(int i=1;i<s;i++)rev[i+s]=(rev[(i>>1)+s]>>1)+((i&1)*(s>>1));
	for(int t=0;t<2;t++)
	for(int s=2;s<=1<<l;s<<=1)
	{
		int tp=pw(3,(mod-1)/s);
		if(!t)tp=pw(tp,mod-2);
		int vl=1;
		for(int i=0;i<s>>1;i++)gr[t][s+i]=vl,vl=1ll*vl*tp%mod;
	}
}
int f[N],g[N],ntt[N];
void dft(int s,int *a,int t)
{
	for(int i=0;i<s;i++)ntt[rev[i+s]]=a[i];
	for(int l=2;l<=s;l<<=1)
	for(int i=0;i<s;i+=l)
	for(int j=0;j<l>>1;j++)
	{
		int v1=ntt[i+j],v2=1ll*ntt[i+j+(l>>1)]*gr[t][j+l]%mod;
		ntt[i+j]=(v1+v2)%mod;ntt[i+j+(l>>1)]=(v1+mod-v2)%mod;
	}
	int tp=t?1:pw(s,mod-2);
	for(int i=0;i<s;i++)a[i]=1ll*ntt[i]*tp%mod;
}

int v1[N],v2[N],v3[N];
int as[N];
void solve(int n,int lb,vector<int> si)
{
	if(n<=64)
	{
		for(int i=0;i<=n;i++)
		{
			as[i+lb]=si[n];
			for(int i=n*2;i>=1;i--)si[i]=(si[i]+si[i-1])%mod;
			for(int i=0;i<n*2;i++)si[i]=(si[i]+si[i+1])%mod;
		}
		return;
	}
	int mid=n>>1,l=1;
	while(l<=n*3)l<<=1;
	for(int i=0;i<l;i++)f[i]=g[i]=0;
	for(int i=0;i<=mid*2;i++)g[i]=1ll*fr[mid*2]*ifr[i]%mod*ifr[mid*2-i]%mod;
	for(int i=0;i<=n*2;i++)f[i]=si[i];
	dft(l,f,1);dft(l,g,1);for(int i=0;i<l;i++)f[i]=1ll*f[i]*g[i]%mod;dft(l,f,0);
	vector<int> s1,s2;
	for(int i=0;i<=(n-mid)*2;i++)s1.push_back(f[mid*2+i]);
	for(int i=0;i<=(mid-1)*2;i++)s2.push_back(si[n-(mid-1)+i]);
	solve(mid-1,lb,s2);
	solve(n-mid,lb+mid,s1);
}
void calc(int n,int m,int s,int *v)
{
	vector<int> s1,s2;
	int tp=n/2;
	for(int i=0;i<=tp*2;i++)
	{
		int rt=s+tp*2-i*2;
		rt=(rt%(2*m+2)+2*m+2)%(2*m+2);
		if(rt%(m+1)==0)s1.push_back(0);
		else if(rt<m+1)s1.push_back(1);
		else s1.push_back(mod-1);
		int rv=0;
		rt=(rt+2*m+1)%(2*m+2);
		if(rt%(m+1)!=0)rv+=rt<m+1?1:-1;
		rt=(rt+2)%(2*m+2);
		if(rt%(m+1)!=0)rv+=rt<m+1?1:-1;
		s2.push_back((mod+rv)%mod);
	}
	solve(tp,0,s1);for(int i=0;i<=tp;i++)v[i*2]=as[i];
	solve(tp,0,s2);for(int i=0;i<=tp;i++)v[i*2+1]=as[i];
}
int main()
{
	init();
	scanf("%d%d%d%d%d%d%d",&n,&l1,&l2,&l3,&s1,&s2,&s3);
	calc(n,l1,s1,v1);
	calc(n,l2,s2,v2);calc(n,l3,s3,v3);
	for(int i=0;i<=n;i++)v1[i]=1ll*ifr[i]*v1[i]%mod,v2[i]=1ll*ifr[i]*v2[i]%mod,v3[i]=1ll*ifr[i]*v3[i]%mod;
	int l=1;while(l<=n*2)l<<=1;
	dft(l,v1,1);dft(l,v2,1);
	for(int i=0;i<l;i++)v1[i]=1ll*v1[i]*v2[i]%mod;dft(l,v1,0);
	int rs=0;
	for(int i=0;i<=n;i++)rs=(rs+1ll*v3[i]*v1[n-i])%mod;
	printf("%d\n",1ll*rs*fr[n]%mod);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 10ms
memory: 15360kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 9ms
memory: 15308kb

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: 32ms
memory: 15584kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 27ms
memory: 15536kb

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: 1370ms
memory: 20120kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

score: 0
Accepted
time: 1376ms
memory: 20168kb

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 1361ms
memory: 19852kb

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: 1358ms
memory: 19784kb

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: 1361ms
memory: 21036kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 1349ms
memory: 20048kb

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: 1353ms
memory: 20936kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 1357ms
memory: 20112kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 1351ms
memory: 20456kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 1351ms
memory: 19844kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 1353ms
memory: 20296kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 1382ms
memory: 20124kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 1382ms
memory: 19816kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 1368ms
memory: 20268kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 1413ms
memory: 20284kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 1409ms
memory: 20348kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 1395ms
memory: 21080kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 1401ms
memory: 20016kb

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: 1390ms
memory: 20164kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 1411ms
memory: 19700kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 1384ms
memory: 20044kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 1390ms
memory: 21028kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 1389ms
memory: 21072kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 1386ms
memory: 20212kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 1387ms
memory: 19928kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 1345ms
memory: 20756kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 1373ms
memory: 20272kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 1347ms
memory: 19960kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 1390ms
memory: 20304kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

score: 0
Accepted
time: 1356ms
memory: 20096kb

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"