QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #730848 | #9536. Athlete Welcome Ceremony | infCraft# | WA | 1ms | 34300kb | C++17 | 4.5kb | 2024-11-09 21:58:39 | 2024-11-09 21:58:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fori(x, y) for (int i=(x);i<=(y);++i)
#define forj(x, y) for (int j=(x);j<=(y);++j)
#define fork(x, y) for (int k=(x);k<=(y);++k)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define debug(x) cerr << #x << " = " << x << endl
const int N = 305;
ll MOD = 1e9+7;
ll dp[2][N][N][N][3];
ll sum[N][N][N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
string str; cin >> str; str = ' '+str;
int now = 0, pre = 1;
// dp[pre][0][0][0][0] = dp[pre][0][0][0][1] = dp[pre][0][0][0][2] = 1;
int cnt = 0;
fori(1, n) {
if (str[i] == '?') cnt++;
for (int a=0;a<=cnt;++a) {
for (int b=0;b<=cnt;++b) {
if (a+b>cnt) break;
for (int c=0;c<=cnt;++c) {
if (a+b+c>cnt) break;
if (str[i] == '?') {
if (i == 1) {
if (a>0) dp[now][a][b][c][0] = 1;
else dp[now][a][b][c][0] = 0;
if (b>0) dp[now][a][b][c][1] = 1;
else dp[now][a][b][c][1] = 0;
if (c>0) dp[now][a][b][c][2] = 1;
else dp[now][a][b][c][2] = 0;
continue;
}
if (a>0) dp[now][a][b][c][0] = (dp[pre][a-1][b][c][1]+dp[pre][a-1][b][c][2])%MOD;
else dp[now][a][b][c][0] = 0;
if (b>0) dp[now][a][b][c][1] = (dp[pre][a][b-1][c][0]+dp[pre][a][b-1][c][2])%MOD;
else dp[now][a][b][c][1] = 0;
if (c>0) dp[now][a][b][c][2] = (dp[pre][a][b][c-1][0]+dp[pre][a][b][c-1][1])%MOD;
else dp[now][a][b][c][2] = 0;
}
else if (str[i] == 'a') {
if (i == 1) {
dp[now][a][b][c][0] = 1;
dp[now][a][b][c][1] = 0;
dp[now][a][b][c][2] = 0;
}
else {
dp[now][a][b][c][0] = (dp[pre][a][b][c][1]+dp[pre][a][b][c][2])%MOD;
dp[now][a][b][c][1] = 0;
dp[now][a][b][c][2] = 0;
}
}
else if (str[i] == 'b') {
if (i == 1) {
dp[now][a][b][c][0] = 0;
dp[now][a][b][c][1] = 1;
dp[now][a][b][c][2] = 0;
}
else {
dp[now][a][b][c][0] = 0;
dp[now][a][b][c][1] = (dp[pre][a][b][c][0]+dp[pre][a][b][c][2])%MOD;
dp[now][a][b][c][2] = 0;
}
}
else if (str[i] == 'c') {
if (i == 1) {
dp[now][a][b][c][0] = 0;
dp[now][a][b][c][1] = 0;
dp[now][a][b][c][2] = 1;
}
else {
dp[now][a][b][c][0] = 0;
dp[now][a][b][c][1] = 0;
dp[now][a][b][c][2] = (dp[pre][a][b][c][1]+dp[pre][a][b][c][2])%MOD;
}
}
}
}
}
swap(now, pre);
}
fori(0, n) forj(0, n) fork(0, n) {
sum[i][j][k] = (dp[pre][i][j][k][0]+dp[pre][i][j][k][1]+dp[pre][i][j][k][2])%MOD;
// debug(sum[i][j][k]);
if (i>0) sum[i][j][k] = (sum[i][j][k]+sum[i-1][j][k])%MOD;
if (j>0) sum[i][j][k] = (sum[i][j][k]+sum[i][j-1][k])%MOD;
if (k>0) sum[i][j][k] = (sum[i][j][k]+sum[i][j][k-1])%MOD;
if (i>0&&j>0) sum[i][j][k] = (sum[i][j][k]-sum[i-1][j-1][k]+MOD)%MOD;
if (i>0&&k>0) sum[i][j][k] = (sum[i][j][k]-sum[i-1][j][k-1]+MOD)%MOD;
if (j>0&&k>0) sum[i][j][k] = (sum[i][j][k]-sum[i][j-1][k-1]+MOD)%MOD;
if (i>0&&j>0&&k>0) sum[i][j][k] = (sum[i][j][k]+sum[i-1][j-1][k-1])%MOD;
}
while (q--) {
int a, b, c;
cin >> a >> b >> c;
cout << sum[a][b][c]%MOD << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 24060kb
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: 0ms
memory: 34300kb
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: 1ms
memory: 7656kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 19984kb
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 0 0 0 0 0 0 0 0 0
result:
wrong answer 2nd lines differ - expected: '1', found: '0'