CF1426F题解

ncwzdlsd · 2023-01-02 14:54:28 · 题解

题干：

给定一个含有 \texttt{abc?} 的字符串,\texttt{?} 可能是 \texttt{abc} 中的任意一个,求所有可能的无 \texttt{?} 字符串中,子序列 \texttt{abc} 出现的次数。

一眼DP。

设 f(i,0) 代表当前序列有多少个“\texttt{?}”，f(i,1) 代表当前序列有多少个“\texttt{a}”，f(i,2) 代表当前序列有多少个“\texttt{ab}”，f(i,3) 代表当前序列有多少个“\texttt{abc}”。

“\texttt{?}”对“\texttt{a}”有贡献，“\texttt{a}”对“\texttt{ab}”有贡献，“\texttt{ab}”对“\texttt{abc}”有贡献。

然后就可以快乐地列状态转移方程DP了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 200000 + 5;
const int mod = 1e9 + 7;
char s[maxn];
ll f[maxn][5];

int main() 
{
    int n;
    cin>>n;
    scanf("%s", &s);
    f[0][0] = 1;
    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j <= 3; ++j) 
        {
            f[i + 1][j] = f[i][j];
        }
        if (s[i] == 'a') 
        {
            f[i + 1][1] = f[i + 1][1] + f[i][0] % mod;
        } 
        else if (s[i] == 'b') 
        {
            f[i + 1][2] = f[i + 1][2] + f[i][1] % mod;
        } 
        else if (s[i] == 'c') 
        {
            f[i + 1][3] = f[i + 1][3] + f[i][2] % mod;
        } 
        else 
        {
            f[i + 1][0] = f[i][0] * 3 % mod;
            for (int j = 1; j <= 3; ++j) 
            {
                f[i + 1][j] = (f[i][j] * 3 % mod + f[i][j - 1] % mod) % mod;
            }
        }
    }
    printf("%lld\n", f[n][3] % mod);
    return 0;
}