题目链接

题目大意

给你一个长为d只包含字符'a','b','c','?' 的字符串，?可以变成a,b,c字符，假如有x个?字符，那么有\(3^x\)个字符串，求所有字符串种子序列包含多少个abc子序列

题目思路

假如没有问号，那么就是一个简单的dp

\(dp[i][1]为前i个位置有多少个a\)

\(dp[i][2]为前i个位置有多少个ab\)

\(dp[i][3]为前i个位置有多少个abc\)

考虑 ’?‘ 会对 dp 的转移产生什么影响，因为 ‘?’ 可以将三种字母全部都表示一遍，所以到了第 i 个位置时，如果前面有 x 个 ' ? ' 的话，那么到达此位置的字符串就会有 \(3^x\) 种，如果不考虑 ' ? ' 的话，碰到一个 ' a ' \(dp[i][1]\) 就需要加一，但现在如果考虑到 ? 的影响，$dp[i][0] $就需要加上 \(3^x\) 才行

再考虑用 ' ? ' 去分别表示三种字母：

1. ' ? ' 表示 ' a ' ：前面仍然有 \(dp[i-1][1]\)个 ' a '，仍然有 \(dp[ i - 1 ][ 2 ]\) 个 ' ab '，仍然有 \(dp[i-1][3]\) 个 ' abc '，多了 3^x 个 a

2. ' ? ' 表示 ' b ' ：前面仍然有 \(dp[i-1][1]\)个 ' a '，仍然有 \(dp[ i - 1 ][ 2 ]\) 个 ' ab '，仍然有 \(dp[i-1][3]\) 个 ' abc '，多了 \(dp[i-1][1]\)个

   ’ ab ‘

3. ' ? ' 表示 ' c ' ：前面仍然有 \(dp[i-1][1]\)个 ' a '，仍然有 \(dp[ i - 1 ][ 2 ]\) 个 ' ab '，仍然有 \(dp[i-1][3]\) 个 ' abc '， 多了\(dp[i-1][2]\)个

   ' abc '

显然可以省略第一维

参考链接

代码

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<vector>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<unordered_map>

#define fi first

#define se second

#define debug printf(" I am here\n");

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;

const double eps=1e-10;

char s[maxn];

ll dp[5];

int d;

signed main(){

    dp[0]=1;

    scanf("%d %s",&d,s+1);

    for(int i=1;i<=d;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{

            for(int j=3;j>=1;j--){

                dp[j]=(dp[j]*3+dp[j-1])%mod;

            }

            dp[0]=dp[0]*3%mod;

        }

    }

    printf("%lld\n",dp[3]);

    return 0;

}