CF1426F Number of Subsequences（简单线性DP）

题意：

给出一个带问号和a b c的序列，询问在不同的子串中出现子序列abc个数的总和。

题解：

简单DP，在问号的地方要实时记录当前序列种类的数量。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
const int mod=1e9+7;
typedef long long ll;
ll a[maxn][3];
ll c[maxn][3];
//分别表示当第i位的数字取j时的前后缀a c 的数量
int n;
string s;
int main () {
    scanf("%d",&n);
    cin>>s;
    ll cnt=1;
    for (int i=1;i<=n;i++) {
        if (s[i-1]=='a') {
            a[i][0]=a[i-1][0]+a[i-1][1]+a[i-1][2]+cnt;a[i][0]%=mod;
        }
        else if (s[i-1]=='b') {
            a[i][1]=a[i-1][0]+a[i-1][1]+a[i-1][2];a[i][1]%=mod;
        }
        else if (s[i-1]=='c') {
            a[i][2]=a[i-1][0]+a[i-1][1]+a[i-1][2];a[i][2]%=mod;
        }
        else {
            a[i][0]=a[i-1][0]+a[i-1][1]+a[i-1][2]+cnt;a[i][0]%=mod;
            a[i][1]=a[i-1][0]+a[i-1][1]+a[i-1][2];a[i][1]%=mod;
            a[i][2]=a[i-1][0]+a[i-1][1]+a[i-1][2];a[i][2]%=mod;
            cnt*=3;
            cnt%=mod;
        }
    }
    cnt=1;
    for (int i=n;i>=1;i--) {
        if (s[i-1]=='a') {
            c[i][0]=c[i+1][0]+c[i+1][1]+c[i+1][2];c[i][0]%=mod;
        }
        else if (s[i-1]=='b') {
            c[i][1]=c[i+1][0]+c[i+1][1]+c[i+1][2];c[i][1]%=mod;
        }
        else if (s[i-1]=='c') {
            c[i][2]=c[i+1][0]+c[i+1][1]+c[i+1][2]+cnt;c[i][2]%=mod;
        }
        else {
            c[i][0]=c[i+1][0]+c[i+1][1]+c[i+1][2];c[i][0]%=mod;
            c[i][1]=c[i+1][0]+c[i+1][1]+c[i+1][2];c[i][1]%=mod;
            c[i][2]=c[i+1][0]+c[i+1][1]+c[i+1][2]+cnt;c[i][2]%=mod;
            cnt*=3;
            cnt%=mod;
        }
    }
    ll ans=0;
    for (int i=1;i<=n;i++) {
        if (s[i-1]=='b'||s[i-1]=='?') {
            ans+=(a[i-1][0]+a[i-1][1]+a[i-1][2])*(c[i+1][0]+c[i+1][1]+c[i+1][2])%mod;
            ans%=mod;
        }
    }
    printf("%lld
",ans);
}