QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#258772#7838. 往日之影zhouhuanyi40 97ms7848kbC++142.3kb2023-11-20 09:33:342023-11-20 09:33:35

Judging History

This is the latest submission verdict.

  • [2023-11-20 09:33:35]
  • Judged
  • Verdict: 40
  • Time: 97ms
  • Memory: 7848kb
Show
  • [2023-11-20 09:33:34]
  • Submitted

answer

#include<iostream>
#include<cstdio>
#define N 1000000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int T,n,sz,tong[N+1],length,a[N+1],mod;
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
struct complex
{
	int a,b;
};
complex zero,res,ans,dp[N+1][2][2],W[4];
complex operator + (complex x,complex y)
{
	return (complex){MD(x.a+y.a),MD(x.b+y.b)};
}
complex operator * (complex x,complex y)
{
	return (complex){MD2(1ll*x.a*y.a%mod-1ll*x.b*y.b%mod),MD(1ll*x.a*y.b%mod+1ll*x.b*y.a%mod)};
}
complex fast_pows(complex a,long long b)
{
	complex res=(complex){1,0},mul=a;
	while (b)
	{
		if (b&1) res=res*mul;
		mul=mul*mul,b>>=1;
	}
	return res;
}
int fast_pow(int a,int b)
{
	int res=1,mul=a;
	while (b)
	{
		if (b&1) res=1ll*res*mul%mod;
		mul=1ll*mul*mul%mod,b>>=1;
	}
	return res;
}
int main()
{
	int x;
	T=read(),mod=read(),W[0]=(complex){1,0},W[1]=(complex){0,1},W[2]=(complex){mod-1,0},W[3]=(complex){0,mod-1};
	while (T--)
	{
		n=read(),length=0,ans=zero;
		for (int i=0;i<=3;++i)
		{
			x=read();
			for (int j=1;j<=x;++j) tong[++length]=i;
		}
		for (int i=0;i<=2;i+=2)
		{
			for (int k=0;k<=n;++k)
				for (int op=0;op<=1;++op)
					for (int op2=0;op2<=1;++op2)
						dp[k][op][op2]=zero;
			dp[0][0][0]=(complex){1,0};
			for (int k=1;k<=n;++k)
				for (int op=0;op<=1;++op)
					for (int op2=0;op2<=1;++op2)
					{
						dp[k][op][op2]=dp[k][op][op2]+dp[k-1][op][op2]*W[(4-i*tong[k]%4)%4];
						if (op) dp[k][op][op2]=dp[k][op][op2]+dp[k-1][op-1][op2]*W[(4-tong[k])%4];
						if (op2) dp[k][op][op2]=dp[k][op][op2]+dp[k-1][op][op2-1]*W[tong[k]];
					}
			for (int op=0;op<=1;++op)
				for (int op2=0;op2<=1;++op2)
				{
					sz=n-op-op2;
					if (sz>=0&&(sz>0||!i))
					{
						res=(complex){fast_pow(2,(1ll*sz*(sz-1))>>1),0};
						if (op) res=res*fast_pows(W[(i+1)%4]+(complex){1,0},sz);
						if (op2) res=res*fast_pows(W[(i+3)%4]+(complex){1,0},sz);
						if (op&&op2) res=res*(complex){2,0};
						ans=ans+dp[n][op][op2]*res;
					}
				}
		}
		printf("%lld\n",1ll*ans.a*fast_pow(4,mod-1-n)%mod*fast_pow(2,mod-1-((1ll*n*(n-1))>>1)%(mod-1))%mod);
	}
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 7652kb

input:

1 998244353
3
1 1 0 1

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7640kb

input:

1 998244353
7
0 2 1 4

output:

998069185

result:

ok single line: '998069185'

Test #3:

score: 0
Accepted
time: 1ms
memory: 7540kb

input:

1 998244353
4
0 1 0 3

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 7672kb

input:

1 998244353
2
1 0 1 0

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 1ms
memory: 7652kb

input:

1 998244353
6
2 1 0 3

output:

997696001

result:

ok single line: '997696001'

Test #6:

score: 0
Accepted
time: 1ms
memory: 7636kb

input:

1 998244353
2
1 0 1 0

output:

0

result:

ok single line: '0'

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #7:

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

input:

1 998244353
40
11 9 9 11

output:

855684614

result:

ok single line: '855684614'

Test #8:

score: 0
Accepted
time: 1ms
memory: 7848kb

input:

1 998244353
39
12 8 7 12

output:

629648158

result:

ok single line: '629648158'

Test #9:

score: 0
Accepted
time: 0ms
memory: 7544kb

input:

1 998244353
38
13 8 9 8

output:

944107686

result:

ok single line: '944107686'

Test #10:

score: 0
Accepted
time: 1ms
memory: 7596kb

input:

1 998244353
37
16 7 7 7

output:

393700837

result:

ok single line: '393700837'

Test #11:

score: 0
Accepted
time: 1ms
memory: 7540kb

input:

4 998244353
10
0 3 2 5
9
2 1 1 5
10
1 2 3 4
9
4 0 3 2

output:

124779131
998235309
124779131
998236023

result:

ok 4 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 7660kb

input:

4 998244353
10
2 1 4 3
9
1 2 4 2
10
3 2 5 0
9
3 2 2 2

output:

124779131
998239593
124778655
998236261

result:

ok 4 lines

Test #13:

score: 0
Accepted
time: 0ms
memory: 7660kb

input:

4 998244353
10
1 4 1 4
9
2 0 5 2
10
3 5 1 1
9
6 1 1 1

output:

623900891
998239355
374338940
998231025

result:

ok 4 lines

Test #14:

score: 0
Accepted
time: 1ms
memory: 7572kb

input:

8 998244353
4
2 1 0 1
4
0 2 0 2
5
0 1 1 3
4
0 1 0 3
5
1 1 0 3
5
0 3 1 1
4
2 2 0 0
5
1 1 2 1

output:

0
0
995319809
0
997269505
995319809
982646785
996294657

result:

ok 8 lines

Test #15:

score: 0
Accepted
time: 1ms
memory: 7660kb

input:

8 998244353
4
2 1 0 1
4
3 0 1 0
4
0 2 2 0
5
2 0 1 2
5
1 2 0 2
5
0 1 1 3
5
0 1 1 3
4
1 1 1 1

output:

0
0
967049217
997269505
0
995319809
995319809
0

result:

ok 8 lines

Test #16:

score: 0
Accepted
time: 0ms
memory: 7604kb

input:

3 998244353
30
1 10 7 12
8
0 3 0 5
2
0 1 0 1

output:

54137262
998208177
0

result:

ok 3 lines

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 10
Accepted
time: 1ms
memory: 7668kb

input:

1 998244353
99
12 22 33 32
15 998244353
7
1 2 2 2
6
1 2 1 2
6
1 1 3 1
7
0 3 1 3
7
1 1 2 3
7
3 1 0 3
6
1 2 1 2
7
1 2 2 2
7
3 3 0 1
6
1 1 3 1
7
5 1 0 1
6
3 0 1 2
6
2 0 0 4
7
2 0 1 4
6
4 1 0 1

output:

940435798

result:

ok single line: '940435798'

Test #18:

score: 0
Accepted
time: 1ms
memory: 7572kb

input:

1 998244353
98
27 29 23 19
15 998244353
7
2 2 1 2
6
0 1 2 3
6
0 2 2 2
6
6 0 0 0
7
4 1 1 1
7
2 1 1 3
7
2 1 1 3
7
2 3 1 1
7
3 3 0 1
6
3 1 1 1
6
3 1 1 1
7
2 1 1 3
6
1 1 3 1
6
1 1 3 1
6
2 0 4 0

output:

147819391

result:

ok single line: '147819391'

Test #19:

score: 0
Accepted
time: 0ms
memory: 7784kb

input:

3 998244353
70
15 17 13 25
20
8 3 4 5
10
3 2 5 0
15 998244353
7
5 1 0 1
6
0 1 4 1
7
1 3 2 1
6
1 0 1 4
7
2 2 1 2
7
2 1 1 3
7
2 3 1 1
6
6 0 0 0
6
3 2 1 0
7
2 3 1 1
7
1 1 2 3
6
2 1 2 1
6
1 2 1 2
6
1 1 1 3
7
2 2 3 0

output:

300715311
500913543
124778655

result:

ok 3 lines

Test #20:

score: 0
Accepted
time: 0ms
memory: 7536kb

input:

3 998244353
70
21 23 11 15
20
5 4 3 8
10
5 1 1 3
15 998244353
6
1 0 3 2
7
3 1 0 3
6
2 2 0 2
7
1 3 0 3
7
2 2 3 0
6
3 0 3 0
6
1 0 3 2
7
1 1 2 3
6
1 1 1 3
7
1 2 0 4
7
2 1 1 3
6
4 0 0 2
6
2 2 2 0
6
2 2 0 2
6
0 1 2 3

output:

367385542
500913543
374339416

result:

ok 3 lines

Test #21:

score: 0
Accepted
time: 1ms
memory: 7788kb

input:

10 998244353
9
2 4 1 2
10
3 4 1 2
10
1 2 3 4
10
2 3 4 1
10
3 1 3 3
9
0 4 3 2
9
2 3 1 3
10
4 2 2 2
9
4 1 1 3
9
2 3 1 3
15 998244353
7
1 3 0 3
6
3 2 1 0
6
0 2 0 4
6
0 4 2 0
7
1 3 0 3
6
1 1 3 1
6
1 4 1 0
7
1 1 2 3
6
2 3 0 1
7
3 1 2 1
6
4 0 2 0
6
2 2 2 0
6
2 1 2 1
7
3 2 2 0
6
0 0 4 2

output:

998236023
124778179
124779131
124778655
374340011
998239355
998236261
374339535
998233643
998236261

result:

ok 10 lines

Test #22:

score: 0
Accepted
time: 0ms
memory: 7664kb

input:

15 998244353
7
3 2 2 0
7
2 2 3 0
6
1 3 1 1
7
1 1 2 3
6
1 3 1 1
7
3 3 0 1
6
2 1 2 1
6
1 2 1 2
6
1 1 1 3
6
4 1 0 1
7
3 2 2 0
6
1 3 1 1
6
0 2 2 2
7
1 3 0 3
7
2 2 1 2

output:

998191041
998191041
998061569
998069185
998061569
998160577
997939713
997939713
997574145
997939713
998191041
998061569
997574145
998145345
998145345

result:

ok 15 lines

Subtask #4:

score: 0
Time Limit Exceeded

Test #23:

score: 10
Accepted
time: 97ms
memory: 7680kb

input:

999 999999001
2
2 0 0 0
3
3 0 0 0
4
4 0 0 0
5
5 0 0 0
6
6 0 0 0
7
7 0 0 0
8
8 0 0 0
9
9 0 0 0
10
10 0 0 0
11
11 0 0 0
12
12 0 0 0
13
13 0 0 0
14
14 0 0 0
15
15 0 0 0
16
16 0 0 0
17
17 0 0 0
18
18 0 0 0
19
19 0 0 0
20
20 0 0 0
21
21 0 0 0
22
22 0 0 0
23
23 0 0 0
24
24 0 0 0
25
25 0 0 0
26
26 0 0 0
27...

output:

499999501
874999126
359374641
919920956
691222454
586081873
33512082
496961574
790501684
206445579
708073277
492142887
486007979
21786019
802052117
198521403
854660059
658779344
904643630
538486221
357736277
949763680
94144464
342842045
695164947
276856011
552666277
813428208
572457238
910726512
177...

result:

ok 999 lines

Test #24:

score: -10
Time Limit Exceeded

input:

1 1000000933
154579
154579 0 0 0

output:

result:

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%
English 繁體中文 简体中文

Server Time: 2025-03-02 16:37:54 | OpenSource Project