[2020.12.6周日]Number of Subsequences

F. Number of Subsequences

题意：给定一个含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
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

#include
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