首先令f[i][j]为到了第j个值为i的贡献.

我们很容易想到没有问号时候的转移方程.

        if(s[i]=='a')
        {
            f[0][i]=(f[0][i-1]+p[cnt])%mod;
        }
        if(s[i]=='b')
        {
            f[1][i]=(f[1][i-1]+f[0][i-1])%mod;
        }
        if(s[i]=='c')
        {
            f[2][i]=(f[2][i-1]+f[1][i-1])%mod;
        }

那么有问号该怎么处理呢?其实也挺简单的,我们知道假如当前为?那么前面的贡献都得*3对吧?因为我?有三种选择'a','b','c'都是会被记录答案的,我们再来考虑第i位,第i位假如为a,那么它的贡献为3^cnt(其中cnt为前面?个数),为什么是这个数呢?可以手画一下,假如前面有两个问号,??我这一位为a,那么我的a会对后面产生多少贡献呢?aaa,aba,aca,baa,bba,bca,caa,cba,cca.9种对吧?假如是b,它的贡献就是前面a的有效数量,c的话同理.如此题目就完美的解决了,是不是挺简单的呢...我居然忘了处理不是?的a的情况debug一晚上,菜哭了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+5,M=3;
ll f[M][N];//到了第几个字母合法字母为b的值.
ll p[N];
char s[N];
ll cnt=0;
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='?') cnt++;
    }
    p[0]=1;
    for(int i=1;i<=cnt;i++) p[i]=p[i-1]*3%mod;
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        f[0][i]=f[0][i-1];
        f[1][i]=f[1][i-1];
        f[2][i]=f[2][i-1];
        if(s[i]=='?')
        {
            f[0][i]=(f[0][i-1]*3ll+p[cnt])%mod;
            f[1][i]=(f[1][i-1]*3ll+f[0][i-1])%mod;
            f[2][i]=(f[2][i-1]*3ll+f[1][i-1])%mod;
            cnt++;
        }
        if(s[i]=='a')
        {
            f[0][i]=(f[0][i-1]+p[cnt])%mod;
        }
        if(s[i]=='b')
        {
            f[1][i]=(f[1][i-1]+f[0][i-1])%mod;
        }
        if(s[i]=='c')
        {
            f[2][i]=(f[2][i-1]+f[1][i-1])%mod;
        }
    }
    cout<<f[2][n]%mod<<endl;
    return 0;
}
/*
7
abc?abc
*/