题意：给定一个含abc和？的序列，每一个？都可以取“a","b"或"c"。比如s="ac?b?c" 我们可以得到["acabac", "acabbc", "acabcc", "acbbac", "acbbbc", "acbbcc", "accbac", "accbbc", "accbcc"]，求出abc子序列的数量。
题解：
我的思路：例如一个“a？c”这样的子序列的贡献是pow（3，num(?)-1)，而所有的可以转成abc的子序列的数量可求。
dp第一维0表示a，1表示ab,2表示abc;第二维表示其中？的个数。
第二种：到当前字母“a”，“b”，“c",这个字母的贡献就是前面出现的？的数量的三次方.
注意点：
1.千万不要觉得是一个很小的运算而不取mod，一道题目这个点可以w三次
2.如果是？里面的代码，为了摒除干扰，应该倒着相加。
tag：dp
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+10;
typedef long long ll;
const int mod=1e9+7;
ll dp[3][4];//第一维0表示a，1表示ab,2表示abc;第二维表示其中？的个数
ll pre[maxn];//pre[i]=pow(3,i)
void add(ll &a,ll b){a=(a+b)%mod;}
int main()
{
int n;cin>>n;
string s;cin>>s;
pre[0]=1;ll cnt=0;//cnt=num(?)
for(int i=0;i<n;i++)
{
if(s[i]=='a')add(dp[0][0],1);
else if(s[i]=='b') add(dp[1][0],dp[0][0]),add(dp[1][1],dp[0][1]);
else if(s[i]=='c') add(dp[2][0],dp[1][0]),add(dp[2][1],dp[1][1]),add(dp[2][2],dp[1][2]);
else
{
add(dp[2][3],dp[1][2]);add(dp[2][2],dp[1][1]);add(dp[2][1],dp[1][0]);
add(dp[1][2],dp[0][1]);add(dp[1][1],dp[0][0]);
add(dp[0][1],1);
add(cnt,1);
}
pre[i+1]=3*pre[i]%mod;
}
ll ans=0;
for(int i=0;i<=3;i++)
{
add(ans,pre[cnt-i]*dp[2][i]%mod);
}
cout<<ans<<endl;
}
我觉得自己的代码写得不够优美，第二个维度可删，参考博客
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
typedef long long ll;
const int mod=1e9+7;
int main()
{
int n;cin>>n;
string s;cin>>s;
ll a=0,ab=0,abc=0,cnt=1;
for(int i=0;i<n;i++)
{
if(s[i]=='a')a=(a+cnt)%mod;
else if(s[i]=='b') ab=(ab+a)%mod;
else if(s[i]=='c') abc=(abc+ab)%mod;
else
{
abc=(abc*3+ab)%mod;
ab=(ab*3+a)%mod;
a=(a*3+cnt)%mod;
cnt=cnt*3%mod;
}
}
cout<<abc%mod<<endl;
}