QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#713870#9536. Athlete Welcome CeremonyEMTzAC ✓402ms668736kbC++202.6kb2024-11-05 20:45:542024-11-05 20:45:55

Judging History

This is the latest submission verdict.

  • [2024-11-05 20:45:55]
  • Judged
  • Verdict: AC
  • Time: 402ms
  • Memory: 668736kb
Show
  • [2024-11-05 20:45:54]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long
#define lson k<<1
#define rson (k<<1)|1
#define debug cout<<666<<endl;
using namespace std;
const int N=1e6+5;
const int M=1e9+7;
int dp[2][155][155][155][4];
int a[305][305][305];
int sum[305][305][305];
void vision()
{
	int n,m;
	cin>>n>>m;
	string s;
	cin>>s;
	s=" "+s+"   ";
	int all=0;
	int op=1;
	for(int i=1;i<=n;i++)
	{
		if(s[i]!='?') 
		{
			continue;
		}
		if(s[i]=='?')all++;
		for(int x=0;x<=min((n+1)/2,all);x++)
		{
			for(int y=0;y<=min((n+1)/2,all-x);y++)
			{
				int z=all-x-y;
				if(z<0) break;
				if(z>(n+1)/2) continue;
				for(int k=1;k<=3;k++)
				{
					int la=-1,ne=-1;
					if(s[i-1]=='a') la=1;
					if(s[i-1]=='b') la=2;
					if(s[i-1]=='c') la=3;
					if(s[i+1]=='a') ne=1;
					if(s[i+1]=='b') ne=2;
					if(s[i+1]=='c') ne=3;
					if(k==la||k==ne) continue;
					if(s[i-1]=='?')
					{
						for(int j=1;j<=3;j++)
						{
							if(k==j) continue;
							if(k==1&&x>0)dp[op][x][y][z][k]+=dp[op^1][x-1][y][z][j];
							if(k==2&&y>0)dp[op][x][y][z][k]+=dp[op^1][x][y-1][z][j];
							if(k==3&&z>0)dp[op][x][y][z][k]+=dp[op^1][x][y][z-1][j];
							dp[op][x][y][z][k]%=M;
						}
					}
					else 
					{
						if(all==1)
						{
							if(k==1&&x>0)dp[op][x][y][z][k]=1;
							if(k==2&&y>0)dp[op][x][y][z][k]=1;
							if(k==3&&z>0)dp[op][x][y][z][k]=1;
							continue;
						}
						for(int j=1;j<=3;j++)
						{
							if(k==1&&x>0)dp[op][x][y][z][k]+=dp[op^1][x-1][y][z][j];
							if(k==2&&y>0)dp[op][x][y][z][k]+=dp[op^1][x][y-1][z][j];
							if(k==3&&z>0)dp[op][x][y][z][k]+=dp[op^1][x][y][z-1][j];
							dp[op][x][y][z][k]%=M;
						}
					}
				}
			}
		}
		op^=1;
	}
	for(int i=0;i<=300;i++)
	{
		for(int j=0;j<=300;j++)
		{
			for(int z=0;z<=300;z++)
			{
				if(i+j+z!=all||i>(n+1)/2||j>(n+1)/2||z>(n+1)/2) a[i+1][j+1][z+1]=0;
				else
				{
					a[i+1][j+1][z+1]=dp[op^1][i][j][z][1]+dp[op^1][i][j][z][2]+dp[op^1][i][j][z][3];
					a[i+1][j+1][z+1]%=M;
				} 
				sum[i+1][j+1][z+1]=a[i+1][j+1][z+1]+sum[i+1][j+1][z-1+1]+sum[i+1][j-1+1][z+1]-sum[i+1][j-1+1][z-1+1]+sum[i-1+1][j+1][z+1]-sum[i-1+1][j+1][z-1+1]-sum[i-1+1][j-1+1][z+1]+sum[i-1+1][j-1+1][z-1+1];
				sum[i+1][j+1][z+1]=(sum[i+1][j+1][z+1]%M+M)%M;;
			}
		}
	}
//	cout<<a[1][1][1]<<"\n";
	while(m--)
	{
		
		int x,y,z;
		cin>>x>>y>>z;
		if(x+y+z<all) 
		{
			cout<<0<<"\n";
			continue;
		}
		int ans=sum[x+1][y+1][z+1];
		ans%=M;
		cout<<ans<<"\n";
	}
	return ;
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t=1;
	// cin>>t;
	while(t--){
		vision();
	}
	return 0;
}
源文件, 语言: C++20

这程序好像有点Bug，我给组数据试试？

詳細信息

Test #1:

score: 100
Accepted
time: 187ms
memory: 447628kb

input:

6 3
a?b??c
2 2 2
1 1 1
1 0 2

output:

3
1
1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 200ms
memory: 449472kb

input:

6 3
??????
2 2 2
2 3 3
3 3 3

output:

30
72
96

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 215ms
memory: 443144kb

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

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

input:

10 10
acab?cbaca
0 2 0
1 1 2
4 2 3
1 1 1
3 5 1
0 5 2
2 2 0
1 2 5
4 3 0
1 1 3

output:

0
1
1
1
1
0
1
1
1
1

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 209ms
memory: 447272kb

input:

10 10
?c?c?cbac?
10 5 1
5 8 7
9 2 6
5 7 1
5 2 6
5 6 5
5 10 3
9 1 10
2 5 9
1 2 9

output:

16
16
11
16
11
16
16
5
11
0

result:

ok 10 lines

Test #6:

score: 0
Accepted
time: 210ms
memory: 446196kb

input:

50 100
?abacbacab?cbcbcb?acabcbabcbcacbababc?caba?acacbca
8 3 8
2 4 8
8 7 3
0 9 2
10 8 7
7 6 5
4 10 2
6 9 3
3 6 6
9 10 8
2 5 8
8 1 0
3 5 0
1 0 6
5 0 8
6 5 5
1 7 9
7 7 10
4 7 5
6 6 4
10 1 2
4 1 7
10 0 8
7 6 3
1 9 1
4 7 2
8 4 0
8 6 1
5 10 4
5 8 2
5 8 4
4 5 9
5 2 1
1 10 9
4 10 1
8 4 3
8 9 9
8 0 1
0 8 0...

output:

8
8
8
0
8
8
6
8
8
8
8
0
0
0
1
8
4
8
8
8
2
4
1
8
1
6
0
2
8
6
8
8
1
4
2
8
8
0
0
8
2
0
8
8
8
4
8
8
8
8
2
0
0
4
8
8
1
8
7
6
7
0
8
8
8
0
4
7
8
4
0
8
0
4
8
8
8
7
8
4
7
2
8
8
8
0
2
2
8
8
8
4
4
0
8
0
8
8
1
1

result:

ok 100 lines

Test #7:

score: 0
Accepted
time: 207ms
memory: 473256kb

input:

50 100
b????????bca?????c?b??ca?acac?b?b???ca?ab???a?a???
35 43 36
12 49 47
7 11 34
38 44 22
42 17 10
49 8 38
18 26 44
6 18 14
28 29 6
48 32 47
29 15 48
1 5 33
24 17 18
10 27 32
19 10 34
2 23 9
14 24 39
46 12 34
9 49 26
21 8 46
43 43 3
31 16 2
8 27 7
24 41 35
17 25 31
0 13 47
24 31 23
33 40 30
36 39...

output:

34272000
31599360
497244
34272000
17637520
12290752
34272000
93044
415832
34272000
34272000
0
34272000
16360704
27933952
0
34272000
33886976
7896832
12290752
718
24
0
34272000
34272000
0
34272000
34272000
34272000
32254720
0
5666944
34256640
34272000
34272000
12290752
30493248
34256640
20630016
0
10...

result:

ok 100 lines

Test #8:

score: 0
Accepted
time: 242ms
memory: 448528kb

input:

100 1000
c?cbababcabacbacbacacbacabcbabababacababcbcab?cbabacbacbcbcacbab?bcabcbcababcacbabacbcb?babcbab?baca
13 11 4
4 17 20
14 5 2
16 14 15
8 12 17
19 5 11
5 17 12
20 7 6
19 10 1
6 5 0
13 1 9
7 17 1
20 4 16
11 12 18
19 2 16
18 1 11
19 16 3
7 1 0
6 9 16
6 9 16
6 20 7
0 16 20
1 2 8
16 5 20
18 14 18
...

output:

16
15
14
16
16
16
16
16
8
2
16
8
16
16
16
16
16
2
16
16
16
0
1
16
16
5
1
5
16
16
16
16
16
15
16
13
16
15
2
16
16
1
8
16
16
16
15
0
16
15
16
16
16
16
8
8
16
16
16
16
16
16
8
16
16
1
8
8
16
16
1
16
1
0
16
2
2
16
7
16
16
8
16
16
16
16
1
16
14
16
16
16
16
5
16
16
14
16
11
16
15
11
2
1
8
16
16
7
16
5
16
...

result:

ok 1000 lines

Test #9:

score: 0
Accepted
time: 215ms
memory: 513756kb

input:

100 1000
?????c??????????????????????????b???a????a?????????????????????????c????????????????????????????????
43 38 20
27 40 32
39 27 33
28 50 43
50 3 46
38 46 14
42 48 10
45 25 28
49 10 49
38 17 42
41 49 22
41 18 44
46 47 25
17 44 35
34 43 22
47 42 32
32 44 40
36 41 24
45 38 45
49 44 18
42 34 32
43...

output:

490475656
143989836
119661929
707864467
10104
219100551
479284703
764218529
903846231
659694548
204287063
105920502
191779504
182802705
215438611
938692318
797581204
903917420
893995828
287222624
578695829
95654849
457810426
709349795
85961844
923330494
783007506
111119718
295402274
241594071
551680...

result:

ok 1000 lines

Test #10:

score: 0
Accepted
time: 238ms
memory: 476420kb

input:

100 1000
c???cacacbcab?cb?acb???ac?bab?bcbcbc?c?bcbcaba??b?ba?c?aca?a?bac?cbcbcba??ca?b????ac?baba?ab?cba?c?c
99 70 32
52 98 84
12 78 77
84 8 87
16 36 0
48 70 100
25 4 15
95 54 35
33 35 90
20 4 69
6 11 76
27 96 48
16 24 18
99 48 1
43 54 35
9 81 75
27 58 52
50 94 14
29 67 27
59 68 53
42 31 46
12 90 2...

output:

380160
380160
226896
64156
0
380160
92
380160
380160
92
0
380160
379648
0
380160
22500
380160
380160
380160
380160
380160
226896
380160
380160
226896
0
380160
380160
380160
380160
152672
380160
5624
226896
380160
380160
379648
0
380160
380160
366848
380160
226896
380160
92
374912
5624
380160
380160
...

result:

ok 1000 lines

Test #11:

score: 0
Accepted
time: 231ms
memory: 444808kb

input:

300 100000
abcacacbabacbcababcacacb?babacbcbacbcababcbcbabcacbcbacacabacacacbacbcbcacbabacbcbcbabcacbababcabcabcabababacbcacbacabcbacbacacacbababababacbcababcbcacacbcbabacabcabababcabacbcbcbabcabacbabacacbcbcacacacbcabcbabcbcabababababcacabcabababcbcbcbcbcabacbabacbabcacbcababacacbcbababababcacacaba...

output:

1
2
2
2
2
1
2
2
2
2
1
1
2
2
2
2
2
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
1
1
2
2
2
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
0
2
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
1
2
2
1
2
2
2
2
1
2
2
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 100000 lines

Test #12:

score: 0
Accepted
time: 239ms
memory: 445240kb

input:

300 100000
bcacbacacabacacbacacbabcabcacabcabcbcaba?cacbabcbacbabcbacacabacabcbacabcacacbcbabcbcabcabacbacbacabacabababcbcbcbabcbacbacabcacacabacbcbababcbcabacbabcbabacabcbabcbababababcbcbabacbacacbcabcabcbcbcbcabacabacacacbcbacabacbabca?acacbcacacbcbabacbcbcabca?babcacbc?acbacabacbcbcbcbacabababacb...

output:

4
4
4
4
0
4
4
4
4
4
4
4
4
4
0
1
3
3
4
4
4
1
4
0
4
0
4
4
4
4
4
4
4
0
4
1
1
4
4
0
4
3
4
4
4
4
4
4
4
3
4
1
1
3
4
0
4
4
3
4
4
4
4
4
4
4
4
4
4
0
4
4
4
3
4
3
4
4
4
1
4
3
0
4
4
4
4
4
0
4
0
4
4
4
4
1
4
4
4
4
4
0
1
4
4
1
4
0
4
3
4
0
4
3
1
0
4
4
1
1
4
4
4
3
4
4
4
3
0
4
1
4
4
4
0
4
4
4
4
1
0
4
1
0
4
4
4
4
4
4
...

result:

ok 100000 lines

Test #13:

score: 0
Accepted
time: 228ms
memory: 470388kb

input:

300 100000
bcbabcab?bab??acacbcabacbacbcacacbabcab?bcbcb?bababcabcabcabca?abcbc?bcacacb?abababcbcbcbcbaba?cba?abcabc?ababacbcbc?acbabcacacbabcab?ca?b?babcbacbacbcbcbacbc?c?cababcacbc?bcbcabcacbabc?acbabcbacac?cbcb?abcbabacabcbacabcacababcbabcbcb??bacbcbacabc?cabacac?cab?cabacacbcacacbabacacabcab?bac...

output:

20336
14528
22504
24576
24576
16992
24576
24576
24576
0
24576
1500
24576
24576
24576
0
23592
7808
24576
0
24576
23592
24576
24576
0
640
24576
2576
24392
24576
624
24576
24576
0
8
24448
8
24576
104
0
24576
24576
24392
0
0
24576
24576
24576
0
24576
24392
24576
24576
24576
23488
24576
24576
24576
24448...

result:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 237ms
memory: 540676kb

input:

300 100000
cbabacacabcaca?abcb?b??cbc??cbacb?acab?b?bcabc?a??bab?a?a?a?ca?acac????c?c?caba?a???bcab?ababababc??babacacacbacabcb?bab?bcab?bacb???ba???c?b?cb?bababac?cb??acacbcba?acaca??bacb?cbc?c?bcbcbab?ba?c??bacacab?b?b?ac??babcbcb?bcbcbcb?c?c?cbac?ba?a?abc?cab?bc?ca?abacaca?abc??ac?aca?a??ca?cac??...

output:

964413406
726709206
0
110704627
192317202
753035749
238645875
836077477
0
0
67075693
196248
337185872
684300992
551066954
512400928
894774207
441158600
632725062
60181080
460670453
301321033
206790308
549405433
258628038
0
719626090
0
800239318
716729053
580760175
749271169
414309213
431703326
12786...

result:

ok 100000 lines

Test #15:

score: 0
Accepted
time: 274ms
memory: 510608kb

input:

300 100000
cbacacacbcba??bc???ab??bca?acabcbcb?cac?babacbac?ba??cbcbac?cb?abacaca?ac?c?caba?ac?cabc?ba?cbaba??ba??abcabac?abab?cabcacbc?cab??aca?bc??babacacab?c?babcacacb?cba?ac?a?abacabcbcbcaca?ab?bcabababc??ababa?abc???acbacbabcac?a?acabcac?cbabac?bacab??c?a??babcbacac??aca?bcba?ab?bcbacbacbabab?b...

output:

868189535
868189535
0
868189535
495627643
0
868189535
929370324
868189535
868189535
1474560
0
0
868189535
868189535
868189535
688551450
868189535
868189535
0
868189535
868189535
868189535
868189535
9381984
868189535
868189535
868189535
868189535
20457120
868189535
868189535
635204610
868189535
86818...

result:

ok 100000 lines

Test #16:

score: 0
Accepted
time: 257ms
memory: 533948kb

input:

300 100000
cbac?cac?cbcbca?abacba?ac?acab????abaca?abcbcabc?c??acb???b?ac??bcb?cacacabac?b?bc?a?b?abcac??a?acacab?bacacab??ca?b?c?acacabcbacacbc?c?acbcabcaca?a?cb?a??abcacab?b?cacb??ac??c?a?bacb?bacbaba?a?bc?babca??bababcababcab?ba?cba??cb?b?abc?cbcab?ba?ca?bacb??ca?bcb??cacbcbca???cbac?bacbc?cac?bc...

output:

63065600
280135711
280135711
280135711
280135711
280135711
280135711
280135711
0
579883317
270080
280135711
0
280135711
280135711
539129922
280135711
280135711
539129922
0
280135711
280135711
280135711
0
280135711
270080
256
280135711
280135711
280135711
280135711
280135711
280135711
631211594
28013...

result:

ok 100000 lines

Test #17:

score: 0
Accepted
time: 311ms
memory: 667252kb

input:

300 100000
??????a?a??c?c?????a??????????b???????????????????????????????????bc?b???????b????????c??????????a????????bc??a????????????c????a?????????????a?????b?????a????????c??ba????b?b???????????c?????????cbc?????????????????b???ab?b????ac?b??c??????c??a??ab???a?????b?????????a??b???????????ba????...

output:

356410997
164744264
978926692
879215541
267745269
399413378
667881560
356410997
818851047
356410997
989150636
266480908
0
356410997
303796242
234869176
137612115
356410997
0
24290767
273625930
411968196
567490332
356410997
0
356410997
807134302
646186244
356410997
356410997
577546772
527886169
35641...

result:

ok 100000 lines

Test #18:

score: 0
Accepted
time: 402ms
memory: 668736kb

input:

300 100000
?a?????????????????b??b??ac?????????????????????b???????c??a??????c????????ac??a???a????a????c????????????bc?????b???c???ab?????????????????????c??????c?b???????a?a?????????c??b??c???b????a?c????????????????c?bc????b???????????b????????bc????c????????????????????a?????????c?????a?????????...

output:

421472289
555100087
555100087
880376766
555100087
0
0
931054200
106211865
993171009
555100087
486740217
555100087
0
555100087
190774849
555100087
336407512
0
0
655515061
555100087
0
309808634
992320113
362042447
0
461962238
830139091
238473131
555100087
0
555100087
555100087
992320113
555100087
1745...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

伺服器時間: 2025-02-07 00:59:09 | 開源專案