QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #737674 | #9536. Athlete Welcome Ceremony | ucup-team1412 | WA | 1490ms | 824156kb | C++14 | 3.2kb | 2024-11-12 16:35:26 | 2024-11-12 16:35:27 |
Judging History
answer
//https://contest.ucup.ac/contest/1821/problem/9536?v=1
//f[i][x][y][p] : 考虑前i个字符，使用j个a，k个b，并且最后一个字符是p
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 305;
ll n , q;
string c, s;
ll f[maxn][maxn][maxn][3];
ll g[maxn][maxn][maxn];
ll cnt[3];
const ll mod = 1e9 + 7;
signed main(){
cin >> n >> q;
cin >> c;
s = "0";
s += c;
for(ll i = 1 ; i <= n;i++){
if(s[i]!='?')cnt[ (ll)(s[i] - 'a') ]++;
}
if(s[1] == '?'){
f[1][2][1][0] = 1;
f[1][1][2][1] = 1;
f[1][1][1][2] = 1;
}
else{
if(s[1] == 'a')f[1][2][1][0] = 1;
if(s[1] == 'b')f[1][1][2][1] = 1;
if(s[1] == 'c')f[1][1][1][2] = 1;
}
for(ll i = 2; i <= n ;i ++){
for(ll x = 1 ; x <= i + 1 ; x++){
for(ll y = 1 ; x + y <= i + 2; y++ ){
// cout << "fdassdas" << endl;
ll z = i + 3 - x - y;
if(s[i] != '?'){
if(s[i] == 'a' && x >= 1){
//f[1][2][1][0]
f[i][x][y][0] = ( f[i - 1][x - 1][y][1] + f[i - 1][x - 1][y][2]+ mod) % mod ;
}
else if ( s[i] == 'b' && y >= 1 ){
f[i][x][y][1] = (f[i - 1][x][y - 1][0] + f[i - 1][x][y - 1][2]+ mod)% mod ;
}
else if ( s[i] == 'c' && z >= 1 ){
f[i][x][y][2] = (f[i - 1][x][y][0] + f[i - 1][x][y][1] + mod) % mod;
}
}
else{
if(s[i - 1] != 'a' && x >= 1 ){//can select a
f[i][x][y][0] = ( f[i - 1][x - 1][y][1] + f[i - 1][x - 1][y][2]+ mod) % mod;
}
if(s[i - 1] != 'b' && y >= 1){//can select b
f[i][x][y][1] = (f[i - 1][x][y - 1][0] + f[i - 1][x][y - 1][2]+ mod) % mod;
}
if(s[i - 1] != 'c' && z >= 1){//can select c
f[i][x][y][2] = (f[i - 1][x][y][0] + f[i - 1][x][y][1] + mod) % mod;
}
}
}
}
}
// cout << f[6][3][3][2] << endl;
for(ll x = 1 ; x <= 2 * n + 1; x++){
for(ll y = 1 ;y <= 2 * n + 1; y++){
for(ll z = 1 ; z <= 2 * n + 1 ; z++){
ll res = 0;
for(ll i = 0 ; i <= 2 ; i++){
res = ( res + f[n][x][y][i] + mod)% mod;
}
// cout << res << endl;
g[x][y][z] = (g[x-1][y][z] + g[x][y-1][z] + g[x][y][z-1] - g[x-1][y-1][z]-g[x-1][y][z-1]-g[x][y-1][z-1] + g[x-1][y-1][z-1] + mod)%mod;
if(x + y + z == n + 3){
g[x][y][z] = (g[x][y][z] + res) % mod;
}
// cout << g[x][y][z] << endl;
}
}
}
while(q--){
ll x,y,z;
cin >> x >> y >> z;
ll ans = g[x + 1 + cnt[0] ][y + 1 + cnt[1] ][z + 1 + cnt[2] ] % mod;
cout << (ans >= 0 ? ans : mod + ans )<< endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16296kb
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: 16436kb
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: 5772kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 2ms
memory: 25284kb
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: 4ms
memory: 25184kb
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: 11ms
memory: 145240kb
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: 7ms
memory: 138884kb
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: 66ms
memory: 342196kb
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: 59ms
memory: 337828kb
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: 55ms
memory: 342532kb
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: -100
Wrong Answer
time: 1490ms
memory: 824156kb
input:
300 100000 abcacacbabacbcababcacacb?babacbcbacbcababcbcbabcacbcbacacabacacacbacbcbcacbabacbcbcbabcacbababcabcabcabababacbcacbacabcbacbacacacbababababacbcababcbcacacbcbabacabcabababcabacbcbcbabcabacbabacacbcbcacacacbcabcbabcbcabababababcacabcabababcbcbcbcbcabacbabacbabcacbcababacacbcbababababcacacaba...
output:
2811 15065 7669 2822 7735 24866 320 4961 326 11084 1257 5 30689 11058 11006 11123 338 1245 14960 30731 1235 2755 4907 24914 11032 4907 2773 4907 19639 11032 2752 19554 11019 9 24904 30605 4889 1270 1272 11077 14975 11097 4934 338 2801 11019 1250 30710 24895 30563 7691 19690 320 19656 19656 24733 195...
result:
wrong answer 1st lines differ - expected: '1', found: '2811'