codeforces-#674-F

codeforces-#674-F

九月 30, 2020

F. Number of Subsequences

题意

给出一个长度为2e5的字符串只含有a,b,c,? 四个字符

可以将”?”替换成a/b/c,

问所有情况下 有多少子序列为”abc”

对于第一个样例：

ac?b?c 共有 24个”abc”子序列

  • “acabac” — there are 2 subsequences “abc”,
  • “acabbc” — there are 4 subsequences “abc”,
  • “acabcc” — there are 4 subsequences “abc”,
  • “acbbac” — there are 2 subsequences “abc”,
  • “acbbbc” — there are 3 subsequences “abc”,
  • “acbbcc” — there are 4 subsequences “abc”,
  • “accbac” — there is 1 subsequence “abc”,
  • “accbbc” — there are 2 subsequences “abc”,
  • “accbcc” — there are 2 subsequences “abc”.

题解

参考题解

设计dp(i,char) 表示第i个字符为b/c 时前i个字符构成的子序列ab/abc有几个

单独统计a的前缀数量和‘?’的前缀数量(记为q)

  • 当这一位的字符为‘a’的时候, 只有a的数量会发生变化。

    这里需要思考的是，‘a’字符的变化不只是单纯的+1，而是$3^q$, q 为这个位置之前的‘?’字符的个数。

  • 当这一位的字符为‘b’的时候 , 只有dp(i,b),(即ab )的数量+a；

  • 当这一位的字符为‘c’的时候 , 只有dp(i,c),(即abc)的数量+b;

  • 当这一位的字符为‘?’的时候 , dp(i,c)=dp(i,c)×3+b,dp(i,b)×3+a,a=3×a+$3^q$;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const int Max=2e5+5;
const int Mod=1e9+7;
int dp[Max][2];///dp(i,b)和dp(i,c)
ll qpow(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=ans*x%Mod;
        x=x*x%Mod;y>>=1;
    }
    return ans;
}
int main(){
    Turnoff;
    int n;cin>>n;
    string s;cin>>s;
    ll a=0,q=0;
    for(int i=1;i<=n;i++){
        if(s[i-1]=='a'){
            a=(a+qpow(3,q))%Mod;
            ///继承前一项的a同时这个a会产生的贡献=前面的?产生的所有子串数个
            dp[i][1]=dp[i-1][1];
            dp[i][0]=dp[i-1][0];
        }
        else if(s[i-1]=='b'){
            dp[i][0]=(dp[i-1][0]+a)%Mod;
            ///继承前一项同时以b为结尾的'ab'子序列多了a个
            dp[i][1]=dp[i-1][1];
        }
        else if(s[i-1]=='c'){
            dp[i][1]=(dp[i-1][1]+dp[i-1][0])%Mod;
            ///继承前一项同时以c为结尾的'abc'子序列多了dp[i-1][0]个
            dp[i][0]=dp[i-1][0];
        }
        else{
            dp[i][1]=(dp[i-1][1]*3ll%Mod+dp[i-1][0])%Mod;
            ///这一位为?那会导致前面的abc的个数多3倍并且当?变为c时子序列abc的个数多了dp[i-1][0]个
            dp[i][0]=(dp[i-1][0]*3ll%Mod+a)%Mod;
            ///这一位为?那会导致前面的ab的个数多3倍并且当?变为b时子序列ab的个数多了a个
            a=(3ll*a%Mod+qpow(3,q))%Mod;
            ///这一位为?那会导致前面的a的个数多3倍并且当?变为a时会增加qpow(3,q)个a
            ///比如a?? 共有3^2个字符串,以?=a为结尾的字符串有3^1个字符串那么最后一位?对a个数的贡献+3^1
            q++;
        }
    }
    cout<<dp[n][1]<<endl;
}