QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #856943 | #9536. Athlete Welcome Ceremony | CharwingHawk | WA | 29ms | 119780kb | C++17 | 11.5kb | 2025-01-14 21:09:30 | 2025-01-14 21:09:32 |
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] = Mod(dp[a+1][b][c][0] + sig - dp[a][b][c][0],mod);
if (s[unknow[nxt]-1] == '?') dp[a][b+1][c][1] = Mod(dp[a][b+1][c][0] + sig - dp[a][b][c][1],mod);
if (s[unknow[nxt]-1] == '?') dp[a][b][c+1][2] = Mod(dp[a][b][c+1][0] + 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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 29ms
memory: 119780kb
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: -100
Wrong Answer
time: 29ms
memory: 117988kb
input:
6 3 ?????? 2 2 2 2 3 3 3 3 3
output:
154 262 696
result:
wrong answer 1st lines differ - expected: '30', found: '154'