题意：
给定一个只包含“abc?”的字符串，其中’?'可以替换为abc的任意一种。 问对于所有可能的串，子序列abc的总和是多少。 答案对1e9+7取模。
数据范围：n<=2e5
code：
d
[0/1/2]表示abc三种前缀的方案数
.
如果没有
?,那么就是一个基本套路题了
.
1.当遇到
'a'的时
:
如果左边为x个
'?',那么此时能构成前缀
'a'的串就会有
3^x种
,
(因为每个x都可以变成a
,b
,c
)
因此转移方程为d
[0]+=3^x
2.当遇到
'b'时
:d
[1]+=d
[0]
3.当遇到
'c'时
:d
[2]+=d
[1]
4.当遇到
'?'时
:
因为之前
'?'有三种取法
,
所以d
[0],d
[1],d
[2]都需要变成三倍
,
同时因为
'?'可以等于a
,b
,c
,因此对
1,2,3的三种情况都需要转移一次
.
code:
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int maxm
=2e5+5;
const int mod
=1e9+7;
char s
[maxm
];
int d
[3];
int n
;
signed main(){
cin
>>n
;
scanf("%s",s
+1);
int p
=1;
for(int i
=1;i
<=n
;i
++){
if(s
[i
]=='a'){
d
[0]+=p
;
}else if(s
[i
]=='b'){
d
[1]+=d
[0];
}else if(s
[i
]=='c'){
d
[2]+=d
[1];
}else if(s
[i
]=='?'){
d
[2]=d
[2]*3+d
[1];
d
[1]=d
[1]*3+d
[0];
d
[0]=d
[0]*3+p
;
p
=p
*3%mod
;
}
d
[0]%=mod
;
d
[1]%=mod
;
d
[2]%=mod
;
}
cout
<<d
[2]<<endl
;
return 0;
}
