QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #702372 | #9536. Athlete Welcome Ceremony | ucup-team3661# | RE | 55ms | 895124kb | C++20 | 2.0kb | 2024-11-02 15:51:52 | 2024-11-02 15:51:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
void add(ll &a , ll b){
a += b;
a %= mod;
}
ll dp[350][350][350][3];
int main(){
int N; cin >> N;
int Q; cin >> Q;
string S; cin >> S;
for(int i = 0; i < 310; i++){
for(int j = 0; j < 310; j++){
for(int k = 0; k < 310; k++){
for(int l = 0; l < 3; l++){
dp[i][j][k][l] = 0;
}
}
}
}
if(S[0] == '?'){
dp[0][1][0][0] = 1;
dp[0][0][1][1] = 1;
dp[0][0][0][2] = 1;
}
else{
if(S[0] == 'a')dp[0][1][0][0] = 1;
if(S[0] == 'b')dp[0][0][1][1] = 1;
if(S[0] == 'c')dp[0][0][0][2] = 1;
}
for(int i = 1; i < N; i++){
for(int j = 0; j <= N; j++){
for(int k = 0; k <= N; k++){
for(int pre = 0; pre < 3; pre++){
if(S[i] == '?'){
if(j-1 >= 0 && pre != 0)add(dp[i][j][k][0] , dp[i-1][j-1][k][pre]);
if(k-1 >= 0 && pre != 1)add(dp[i][j][k][1] , dp[i-1][j][k-1][pre]);
if(pre != 2)add(dp[i][j][k][2] , dp[i-1][j][k][pre]);
}
else{
ll d = S[i] - 'a';
if(d == pre)continue;
if(d == 0){
if(j-1 >= 0)add(dp[i][j][k][0] , dp[i-1][j-1][k][pre]);
}
if(d == 1){
if(k-1 >= 0)add(dp[i][j][k][1] , dp[i-1][j][k-1][pre]);
}
if(d == 2){
add(dp[i][j][k][2] , dp[i-1][j][k][pre]);
}
}
}
}
}
}
vector<vector<ll>> sum(N+20 , vector<ll>(N+20));
for(int i = 0; i <= N; i++){
for(int j = 0; j <= N; j++){
add(sum[i][j+1] , sum[i][j]);
for(int k = 0; k < 3; k++)add(sum[i][j+1] , dp[N-1][i][j][k]);
}
}
int ba = 0, bb = 0, bc = 0;
for(int i = 0; i < N; i++){
if(S[i] == 'a')ba++;
if(S[i] == 'b')bb++;
if(S[i] == 'c')bc++;
}
while(Q--){
int A,B,C; cin >> A >> B >> C;
A += ba;
B += bb;
C += bc;
ll ans = 0;
for(int a = 0; a <= A; a++){
if(B+1 <= N-a-C)continue;
add(ans , sum[a][min(B+1,N+1)]);
add(ans , mod - sum[a][max(0 , N-a-C)]);
}
cout << ans << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 24ms
memory: 895124kb
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: 48ms
memory: 894192kb
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: 16ms
memory: 894644kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 43ms
memory: 893872kb
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: 48ms
memory: 893608kb
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: 35ms
memory: 894520kb
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: 28ms
memory: 894216kb
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: 40ms
memory: 893468kb
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: 55ms
memory: 893740kb
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: -100
Runtime Error
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 ...