CF 1426 F. Number of Subsequences(计数dp)
Problem - F - Codeforces
大意：给出一个字符串 ， 每个字符串包含 ‘a’ , ‘b’ , ‘c’ , ‘?’ 四种字符 ， 问把所有 ‘?’ 替换成其余三种字符后生成的所有字符串中 ， 含有 “abc” 子序列的个数有多少个。
思路：先考虑没有’?’的情况 , 那么会有一个经典的动态规划状态设计 ， 那就是
dp[i][0/1/2] 表示以 i 结尾的前缀 子序列'a' 'ab' 'abc' 的个数
if(i == a)
dp[i][0] = dp[i - 1][0] + 1
dp[i][1] = dp[i - 1][1]
dp[i][2] = dp[i - 1][2]
if(i == b)
dp[i][0] = dp[i - 1][0]
dp[i][1] = dp[i - 1][1] + dp[i - 1][0]
dp[i][2] = dp[i - 1][2]
if(i == c)
dp[i][0] = dp[i - 1][0]
dp[i][1] = dp[i - 1][1]
dp[i][2] = dp[i - 1][2] + dp[i - 1][1]
那么我们现在考虑加上‘?’的情况 ， 依旧使用当前的状态设计
我们考虑 当 i = ’a‘ 的时候 ， 显然贡献并不是 ＋ 1 ， 前面 n 个 ’?‘ ， 会产生 3^n 个子串 ， 每个子串都能产生一个贡献
i = ‘b’ 和 i = ‘c’ 的时候可以从前面进行转移。
i = ‘?’ 的时候我们模拟一下 ， 会发现每个前缀串数量都会变成原来的三倍 ， 然后相当于在每个前缀串上都各加上 ‘a’ ‘b’ ‘c’。
举例：
原串
ab?c?a
在到第二个问号时
abac
abbc
abcc
会变成
abaca
abbca
abcca
abacb
abbcb
abccb
abacc
abbcc
abccc
相当于原来的每个前缀先变成三倍 ， 然后在原来的每个前缀上分别加上三个字母
转移方程：
if(i == a)
dp[i][0] = dp[i - 1][0] + 3^cnt
dp[i][1] = dp[i - 1][1]
dp[i][2] = dp[i - 1][2]
if(i == b)
dp[i][0] = dp[i - 1][0]
dp[i][1] = dp[i - 1][1] + dp[i - 1][0]
dp[i][2] = dp[i - 1][2]
if(i == c)
dp[i][0] = dp[i - 1][0]
dp[i][1] = dp[i - 1][1]
dp[i][2] = dp[i - 1][2] + dp[i - 1][1]
if(i == '?')
dp[i][0] = 3 * dp[i - 1][0] + 3^cnt
dp[i][1] = 3 * dp[i - 1][1] + dp[i - 1][0]
dp[i][0] = 3 * dp[i - 1][0] + dp[i - 1][1]
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
int n , cnt;
string s;
int dp[N][3];
inline int qp(int x , int y , int p){
int res = 1 % p;
x = x % p;
while(y){
if(y & 1) res = res * x % p;
x = x * x % p;
y >>= 1;
}
return res;
}
signed main(){
cin >> n >> s;
for(int i = 1 ; i <= n ; i ++){
if(s[i - 1] == '?'){
dp[i][0] = (dp[i - 1][0] * 3 % mod + qp(3 , cnt , mod)) % mod;
dp[i][1] = (dp[i - 1][1] * 3 % mod + dp[i - 1][0]) % mod;
dp[i][2] = (dp[i - 1][2] * 3 % mod + dp[i - 1][1]) % mod;
cnt += 1;
}
if(s[i - 1] == 'a'){
dp[i][0] = (dp[i - 1][0] + qp(3 , cnt , mod)) % mod;
dp[i][1] = dp[i - 1][1];
dp[i][2] = dp[i - 1][2];
}
if(s[i - 1] == 'b'){
dp[i][0] = dp[i - 1][0];
dp[i][1] = (dp[i - 1][1] + dp[i - 1][0]) % mod;
dp[i][2] = dp[i - 1][2];
}
if(s[i - 1] == 'c'){
dp[i][0] = dp[i - 1][0];
dp[i][1] = dp[i - 1][1];
dp[i][2] = (dp[i - 1][2] + dp[i - 1][1]) % mod;
}
}
cout << dp[n][2];
return 0;
}