QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704866#9536. Athlete Welcome Ceremonyucup-team4967#WA 3ms11144kbC++172.7kb2024-11-02 21:19:242024-11-02 21:19:25

Judging History

This is the latest submission verdict.

  • [2024-11-02 21:19:25]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 11144kb
  • [2024-11-02 21:19:24]
  • Submitted

answer

	#include "bits/stdc++.h"

	using namespace std;

	#define REP(i, n) for(int i = 0;i < n;i++)
	#define REPR(i, n) for(int i = n;i >= 0;i--)
	#define FOR(i, m, n) for(ll i = m;i < n;i++)
	#define FORR(i, m, n) for(ll i = m;i >= n;i--)
	#define REPO(i, n) for(ll i = 1;i <= n;i++)
	#define ll long long
	#define INF (ll)1ll << 60
	#define MINF (-1 * INF)
	#define ALL(n) n.begin(),n.end()
	#define MOD (ll)1000000007
	#define P pair<ll, ll>

	#define pl(a, b) a = (a + b) % (ll)1000000007
	ll dp[305][305][305][3], v[305][305], t[305][305];
	ll mod = (ll)1000000007;
	ll n, q, u;
	int main() {
		
		cin >> n >> q;
		string s;
		cin >> s;
		REP(i, n) if(s[i] == '?')u++;
		REP(i, n){
			REP(j, i + 1){
				REP(k, i + 1){
					if(i == 0){
						if(s[i] == 'a') pl(dp[i + 1][j][k][0], 1);
						if(s[i] == 'b') pl(dp[i + 1][j][k][1], 1);
						if(s[i] == 'c') pl(dp[i + 1][j][k][2], 1);
						if(s[i] == '?') {
							pl(dp[i + 1][j + 1][k][0], 1);
							pl(dp[i + 1][j][k + 1][1], 1);
							pl(dp[i + 1][j][k][2], 1);
						}
					}
					else{
						if(s[i] == 'a') {
							pl(dp[i + 1][j][k][0], dp[i][j][k][1]);
							pl(dp[i + 1][j][k][0], dp[i][j][k][2]);
						}
						if(s[i] == 'b') {
							pl(dp[i + 1][j][k][1], dp[i][j][k][0]);
							pl(dp[i + 1][j][k][1], dp[i][j][k][2]);
						}
						if(s[i] == 'c') {
							pl(dp[i + 1][j][k][2], dp[i][j][k][0]);
							pl(dp[i + 1][j][k][2], dp[i][j][k][1]);
						}
						else if(s[i] == '?'){
							pl(dp[i + 1][j + 1][k][0], dp[i][j][k][1]);
							pl(dp[i + 1][j + 1][k][0], dp[i][j][k][2]);
							pl(dp[i + 1][j][k + 1][1], dp[i][j][k][0]);
							pl(dp[i + 1][j][k + 1][1], dp[i][j][k][2]);
							pl(dp[i + 1][j][k][2], dp[i][j][k][0]);
							pl(dp[i + 1][j][k][2], dp[i][j][k][1]);
						}
					}
				}
			}
		}
		REP(i, 302){
			REP(j, 302){
				REP(k, 3){
					pl(v[i][j], dp[n][i][j][k]);
					pl(t[i][j], dp[n][i][j][k]);
				}
			}
		}
		REP(i, 302){
			REP(j, 302){
				pl(v[i][j + 1], v[i][j]);
			}
		}
		REP(n, 604){
			REP(i, n){
				if(i + 1 > 302 or n - i > 302)continue;
				pl(v[n - i - 1][i + 1], v[n - i][i]);
			}
		}

		REP(i, 302){
			REP(j, 302){
				pl(t[i][j + 1], t[i][j]);
			}
		}
		REP(i, 302){
			REP(j, 302){
				pl(t[i + 1][j], t[i][j]);
			}
		}
		REP(qq, q){
			ll a, b, c;
			cin >> a >> b >> c;
			ll m = max(0ll, u - c);

			ll ans = t[a][b];
			if(m - b - 2 >= 0) ans = (ans - t[m - b - 2][b] + mod) % mod;
			if(m >= 1){
				if(m - b - 1 >= 0) ans = (ans - v[m - b - 1][b] + mod) % mod;
				else ans = (ans - v[0][m - 1] + mod) % mod;
			}
			if(m - a - 2 >= 0) ans = (ans + t[a + 1][m - a - 2]) % mod;
			
			cout << ans << endl;
		}


	}


详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 5112kb

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: 3ms
memory: 5120kb

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: 0ms
memory: 4956kb

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 3ms
memory: 5272kb

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: 3ms
memory: 5480kb

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

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
1000000006
8
8
6
8
8
8
8
0
1
0
1
8
4
8
8
8
2
4
1
8
2
6
0
2
8
6
8
8
1
4
2
8
8
0
1000000003
8
2
0
8
8
8
4
8
8
8
8
2
0
3
4
8
8
1
8
7
6
7
0
8
8
8
0
4
7
8
4
3
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:

wrong answer 4th lines differ - expected: '0', found: '1000000006'