QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#716894#9536. Athlete Welcome Ceremonyafeng111#WA 176ms182740kbC++202.4kb2024-11-06 16:17:332024-11-06 16:17:34

Judging History

This is the latest submission verdict.

  • [2024-11-06 16:17:34]
  • Judged
  • Verdict: WA
  • Time: 176ms
  • Memory: 182740kb
Show
  • [2024-11-06 16:17:33]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+7;
const int mod=1000000007;
const int M=2e6+7;

int dp[2][170][170][170][3],pre[301][301][301];
int n,q,cnt[3];
string s;

int ct(int a,int b,int c)
{
	if(a<0||b<0||c<0)return 0;
	return pre[a][b][c];
}

void add(int&a, int b)
{
	a+=b;
	if(a>=mod)a-=mod;
}

void modify(int tag,int a,int b,int c,int now)
{
	for(int j=0;j<3;j++)
	{
		if(j!=now)
		{
			if(now==0&&a)
				add(dp[tag][a][b][c][now],dp[tag^1][a-1][b][c][j]);
			else if(now==1&&b)
				add(dp[tag][a][b][c][now],dp[tag^1][a][b-1][c][j]);
			else if(now==2&&c)
				add(dp[tag][a][b][c][now],dp[tag^1][a][b][c-1][j]);
		}
	}
}

void solve()
{
	cin>>n>>q>>s;
	s=' '+s;
	if(s[1]=='?')
	{
		dp[1][1][0][0][0]=1;
		dp[1][0][1][0][1]=1;
		dp[1][0][0][1][2]=1;
	}
	else if(s[1]=='a')
		dp[1][1][0][0][0]=1;
	else if(s[1]=='b')
		dp[1][0][1][0][1]=1;
	else 
		dp[1][0][0][1][2]=1;
	cnt[s[1]-'a']++;
	
	for(int i=2;i<=n;i++)
	{
		cnt[s[i]-'a']++;
		int tag=i&1;
		for(int a=0;a<165;a++)
			for(int b=0;b<165&&a+b<=i;b++)
				{
					int c=i-a-b;
					dp[tag][a][b][c][0]=0;
					dp[tag][a][b][c][1]=0;
					dp[tag][a][b][c][2]=0;
					if(s[i]=='?')
					{
						modify(tag,a,b,c,0);
						modify(tag,a,b,c,1);
						modify(tag,a,b,c,2);
					}
					else if(s[i]=='a')
						modify(tag,a,b,c,0);
					else if(s[i]=='b')
						modify(tag,a,b,c,1);
					else 
						modify(tag,a,b,c,2);
				}
	}
//	for(int a=0;a<165;a++)
//		for(int b=0;b<165;b++)
//			for(int c=0;c<165;c++)
//				for(int i=0;i<3;i++)
//				if(dp[n&1][a][b][c][i])
//				{
//					cout<<a<<' '<<b<<' '<<c<<' '<<(char)('a'+i)<<' '<<dp[n&1][a][b][c][i]<<endl;
//				}
	int tag=n&1;
	for(int a=0;a<=300;a++)
		for(int b=0;b<=300;b++)
			for(int c=0;c<=300;c++)
			{
				int tot=0;
				if(a+b+c==n)
					for(int j=0;j<3;j++)
					{
						tot+=dp[tag][a][b][c][j];
						if(tot>=mod)tot-=mod;
					}
				tot=(1ll*tot+ct(a-1,b,c)+ct(a,b-1,c)+ct(a,b,c-1)-ct(a-1,b-1,c)-ct(a,b-1,c-1)-ct(a-1,b,c-1)+ct(a-1,b-1,c-1))%mod;
				pre[a][b][c]=tot;
			}
				
	while(q--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		a=min(300,a+cnt[0]);
		b=min(300,b+cnt[1]);
		c=min(300,c+cnt[2]);
		cout<<pre[a][b][c]<<'\n';
	}
	
	
}

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

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


*/

int main()
{
	int t=1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 169ms
memory: 117896kb

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: 174ms
memory: 116460kb

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: 171ms
memory: 113600kb

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 168ms
memory: 118576kb

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: 176ms
memory: 117656kb

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: 164ms
memory: 145764kb

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: 165ms
memory: 146160kb

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: 174ms
memory: 181560kb

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: -100
Wrong Answer
time: 166ms
memory: 182740kb

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
-856010171
-880338078
-292135540
10104
219100551
-520715304
-235781478
-96153776
-340305459
204287063
-894079505
191779504
182802705
-784561396
-61307689
797581204
903917420
-106004179
287222624
-421304178
95654849
-542189581
-290650212
85961844
-76669513
783007506
-888880289
295402274
241...

result:

wrong answer 2nd lines differ - expected: '143989836', found: '-856010171'
English 繁體中文 简体中文

服务器时间: 2025-02-07 11:03:55 | 开源项目