QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #856939 | #9536. Athlete Welcome Ceremony | CharwingHawk | WA | 37ms | 119652kb | C++17 | 11.5kb | 2025-01-14 21:07:06 | 2025-01-14 21:07:06 |
Judging History
answer
//https://mirror.codeforces.com/group/hiEODjQtaL/contest/105486/problem/B
#include <bits/stdc++.h>
using namespace std;
#define int long long
//宏函数
#define KE ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define flt(x) cout << fixed << setprecision(x);
#define all(x) (x).begin(), (x).end()
#define bcount(t) __builtin_popcount(t)
#define legal(x,lo,hi) (lo <= x && x <= hi)
#define Mod(x,m) (((x) % m + m) % m)
#define flip(x) reverse(x)
#define lowbit(x) (x&(-x))
#define bemax(x,y) x = max(x, y)
#define pb push_back
#define elif else if
#define endl '\n'
//调试部分
#define AA cerr << "AA" << endl;
#define __ << " " <<
//常量部分
const int N = 1e5 + 10;
const int inf = 1e18;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
int dp[155][155][155][3];
int pre[155][155][155];
void solve(){
int n,q; cin>>n>>q;
string s; cin>>s;
int l = s.size();
int unknow[305],cnt = 0;
for(int cur=0;cur<s.size();cur++){
if (s[cur] == '?') unknow[++cnt] = cur;
}
for(int a = 0;a<=151;a++){
for(int b = 0;b<=151;b++){
for(int c = 0;c<=151;c++){
for(int cur = 0;cur<=2;cur++){
dp[a][b][c][cur] = 0;
}
}
}
}
if (!legal(unknow[1]-1,0,l-1)){
if (!legal(unknow[1]+1,0,l-1)){
dp[1][0][0][0] = 1; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 1; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 1;
}
else{
if (s[unknow[1]+1] == 'a'){
dp[1][0][0][0] = 0; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 1; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 1;
}
if (s[unknow[1]+1] == 'b'){
dp[1][0][0][0] = 1; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 0; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 1;
}
if (s[unknow[1]+1] == 'c'){
dp[1][0][0][0] = 1; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 1; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 0;
}
if (s[unknow[1]+1] == '?'){
dp[1][0][0][0] = 1; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 1; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 1;
}
}
}
else{
if (s[unknow[1]-1] == 'a'){
if (!legal(unknow[1]+1,0,l-1) || (legal(unknow[1]+1,0,l-1) && s[unknow[1]+1] == '?')){
dp[1][0][0][0] = 0; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 1; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 1;
}
else{
if (s[unknow[1]+1] == 'a'){
dp[1][0][0][0] = 0; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 1; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 1;
}
if (s[unknow[1]+1] == 'b'){
dp[1][0][0][0] = 0; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 0; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 1;
}
if (s[unknow[1]+1] == 'c'){
dp[1][0][0][0] = 0; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 1; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 0;
}
}
}
if (s[unknow[1]-1] == 'b'){
if (!legal(unknow[1]+1,0,l-1) || (legal(unknow[1]+1,0,l-1) && s[unknow[1]+1] == '?')){
dp[1][0][0][0] = 1; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 0; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 1;
}
else{
if (s[unknow[1]+1] == 'a'){
dp[1][0][0][0] = 0; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 0; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 1;
}
if (s[unknow[1]+1] == 'b'){
dp[1][0][0][0] = 1; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 0; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 1;
}
if (s[unknow[1]+1] == 'c'){
dp[1][0][0][0] = 1; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 0; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 0;
}
}
}
if (s[unknow[1]-1] == 'c'){
if (!legal(unknow[1]+1,0,l-1) || (legal(unknow[1]+1,0,l-1) && s[unknow[1]+1] == '?')){
dp[1][0][0][0] = 1; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 1; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 0;
}
else{
if (s[unknow[1]+1] == 'a'){
dp[1][0][0][0] = 0; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 1; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 0;
}
if (s[unknow[1]+1] == 'b'){
dp[1][0][0][0] = 1; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 0; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 0;
}
if (s[unknow[1]+1] == 'c'){
dp[1][0][0][0] = 1; dp[1][0][0][1] = 0; dp[1][0][0][2] = 0;
dp[0][1][0][0] = 0; dp[0][1][0][1] = 1; dp[0][1][0][2] = 0;
dp[0][0][1][0] = 0; dp[0][0][1][1] = 0; dp[0][0][1][2] = 0;
}
}
}
}
for(int a = 0;a<=150;a++){
for(int b = 0;b<=150;b++){
for(int c = 0;c<=150;c++){
int nxt = a+b+c+1;
int sig = (dp[a][b][c][0] + dp[a][b][c][1] + dp[a][b][c][2]) %mod;
if (nxt <= 1) continue;
if (nxt > cnt) break;
if (!legal(unknow[nxt]+1,0,l-1) || (legal(unknow[nxt]+1,0,l-1) && s[unknow[nxt]+1] == '?')){
if (s[unknow[nxt]-1] == 'a') dp[a][b+1][c][1] = (dp[a][b+1][c][1] + sig) %mod;
if (s[unknow[nxt]-1] == 'a') dp[a][b][c+1][2] = (dp[a][b][c+1][2] + sig) %mod;
if (s[unknow[nxt]-1] == 'b') dp[a+1][b][c][0] = (dp[a+1][b][c][0] + sig) %mod;
if (s[unknow[nxt]-1] == 'b') dp[a][b][c+1][2] = (dp[a][b][c+1][2] + sig) %mod;
if (s[unknow[nxt]-1] == 'c') dp[a+1][b][c][0] = (dp[a+1][b][c][0] + sig) %mod;
if (s[unknow[nxt]-1] == 'c') dp[a][b+1][c][1] = (dp[a][b+1][c][1] + sig) %mod;
if (s[unknow[nxt]-1] == '?') dp[a+1][b][c][0] = (dp[a+1][b][c][0] + sig - dp[a][b][c][0]) %mod;
if (s[unknow[nxt]-1] == '?') dp[a][b+1][c][1] = (dp[a][b+1][c][1] + sig - dp[a][b][c][1]) %mod;
if (s[unknow[nxt]-1] == '?') dp[a][b][c+1][2] = (dp[a][b][c+1][2] + sig - dp[a][b][c][2]) %mod;
}
else{
if (s[unknow[nxt]+1] == 'a'){
if (s[unknow[nxt]-1] == 'a') dp[a][b+1][c][1] = (dp[a][b+1][c][1] + sig) %mod;
if (s[unknow[nxt]-1] == 'a') dp[a][b][c+1][2] = (dp[a][b][c+1][2] + sig) %mod;
if (s[unknow[nxt]-1] == 'b') dp[a][b][c+1][2] = (dp[a][b][c+1][2] + sig) %mod;
if (s[unknow[nxt]-1] == 'c') dp[a][b+1][c][1] = (dp[a][b+1][c][1] + sig) %mod;
if (s[unknow[nxt]-1] == '?') dp[a][b+1][c][1] = (dp[a][b+1][c][1] + sig - dp[a][b][c][1]) %mod;
if (s[unknow[nxt]-1] == '?') dp[a][b][c+1][2] = (dp[a][b][c+1][2] + sig - dp[a][b][c][2]) %mod;
}
if (s[unknow[nxt]+1] == 'b'){
if (s[unknow[nxt]-1] == 'a') dp[a][b][c+1][2] = (dp[a][b][c+1][2] + sig) %mod;
if (s[unknow[nxt]-1] == 'b') dp[a+1][b][c][0] = (dp[a+1][b][c][0] + sig) %mod;
if (s[unknow[nxt]-1] == 'b') dp[a][b][c+1][2] = (dp[a][b][c+1][2] + sig) %mod;
if (s[unknow[nxt]-1] == 'c') dp[a+1][b][c][0] = (dp[a+1][b][c][0] + sig) %mod;
if (s[unknow[nxt]-1] == '?') dp[a+1][b][c][0] = (dp[a+1][b][c][0] + sig - dp[a][b][c][0]) %mod;
if (s[unknow[nxt]-1] == '?') dp[a][b][c+1][2] = (dp[a][b][c+1][2] + sig - dp[a][b][c][2]) %mod;
}
if (s[unknow[nxt]+1] == 'c'){
if (s[unknow[nxt]-1] == 'a') dp[a][b+1][c][1] = (dp[a][b+1][c][1] + sig) %mod;
if (s[unknow[nxt]-1] == 'b') dp[a+1][b][c][0] = (dp[a+1][b][c][0] + sig) %mod;
if (s[unknow[nxt]-1] == 'c') dp[a+1][b][c][0] = (dp[a+1][b][c][0] + sig) %mod;
if (s[unknow[nxt]-1] == 'c') dp[a][b+1][c][1] = (dp[a][b+1][c][1] + sig) %mod;
if (s[unknow[nxt]-1] == '?') dp[a+1][b][c][0] = (dp[a+1][b][c][0] + sig - dp[a][b][c][0]) %mod;
if (s[unknow[nxt]-1] == '?') dp[a][b+1][c][1] = (dp[a][b+1][c][1] + sig - dp[a][b][c][1]) %mod;
}
}
}
}
}
for(int a = 0;a<=150;a++){
for(int b = 0;b<=150;b++){
for(int c = 0;c<=150;c++){
if (a+b+c == cnt){
pre[a][b][c] = (dp[a][b][c][0] + dp[a][b][c][1] + dp[a][b][c][2]) %mod;
}
}
}
}
for(int a = 0;a<=150;a++){
for(int b = 0;b<=150;b++){
for(int c = 1;c<=150;c++){
pre[a][b][c] = (pre[a][b][c] + pre[a][b][c-1]) %mod;
}
}
}
for(int a = 0;a<=150;a++){
for(int b = 1;b<=150;b++){
for(int c = 0;c<=150;c++){
pre[a][b][c] = (pre[a][b][c] + pre[a][b-1][c]) %mod;
}
}
}
for(int a = 1;a<=150;a++){
for(int b = 0;b<=150;b++){
for(int c = 0;c<=150;c++){
pre[a][b][c] = (pre[a][b][c] + pre[a-1][b][c]) %mod;
}
}
}
for(int cur=0;cur<q;cur++){
int a,b,c; cin>>a>>b>>c;
a = min(150ll,a);
b = min(150ll,b);
c = min(150ll,c);
cout<<pre[a][b][c]<<endl;
}
}
signed main(){
KE;
int T = 1;
// cin >> T;
// flt(3);
while(T--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 36ms
memory: 117864kb
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: 37ms
memory: 118576kb
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: 36ms
memory: 117920kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 32ms
memory: 117856kb
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: 32ms
memory: 117856kb
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: 34ms
memory: 119652kb
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: 33ms
memory: 119124kb
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: 34ms
memory: 118776kb
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: 36ms
memory: 117920kb
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:
-509524351 -856010171 119661929 -292135540 10104 219100551 479284703 -235781478 -96153776 -340305459 204287063 105920502 191779504 182802705 215438611 -61307689 797581204 903917420 893995828 287222624 578695829 95654849 -542189581 -290650212 85961844 -76669513 -216992501 111119718 295402274 24159407...
result:
wrong answer 1st lines differ - expected: '490475656', found: '-509524351'