CodeForces Round674 F - Number of Subsequences 组合,DP
题意
给出一个长度为(n)的字符串,仅包含(a,b,c,?)组成,每个'?'都可以变成三个字母之一。
如果有(k)个(?)。这(3^k)个可能的字符串中,共有多少个含有(abc)的子序列。
分析
如果不考虑(?)的存在,就是一个经典的(dp)问题,只需要(dp[i][0-3])表示前(i)个字符中,有(a,ab,abc)的个数。
再考虑(?)的存在影响
假设前面存在(x)个(?)
[1. quad? 表示 a:多了3^x个a\
2. quad? 表示 b:多了dp[i - 1][0] 个b\
3.quad ? 表示 c: 多了dp[i - 1][1] 个c
]
注意到第一维可以滚动
直接写就行了。
代码
ll dp[10];
char s[maxn];
int main() {
int n = readint();
//getchar();
scanf("%s", s);
dp[0] = 1ll;
for (int i = 0; i < n; i++) {
if (s[i] == 'a')
dp[1] = (dp[1] + dp[0]) % MOD;
else if (s[i] == 'b')
dp[2] = (dp[2] + dp[1]) % MOD;
else if (s[i] == 'c')
dp[3] = (dp[3] + dp[2]) % MOD;
else if (s[i] == '?') {
dp[3] = (3 * dp[3] % MOD + dp[2]) % MOD;
dp[2] = (3 * dp[2] % MOD + dp[1]) % MOD;
dp[1] = (3 * dp[1] % MOD + dp[0]) % MOD;
dp[0] = 3 * dp[0] % MOD;
}
}
Put(dp[3]);
}