题解 | 躲藏

经典子序列匹配数量问题

力扣原题：https://leetcode.cn/problems/distinct-subsequences/

2023年蓝桥杯C++ B组国赛第一道填空题也出过，算是经典题中的经典题了。

设是当前处理的字符串中，可以构成子序列为 的前j项的方案数。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+7;
typedef unsigned long long ll;
const ll M=2000120420010122;
ll f[5];//前i项出现了前j字符串的方案书
string s,t="cwbc";
int n;
void solve(){
    while(getline(cin,s)){
        memset(f,0,sizeof f);
        f[0]=1;
        n=s.size();
        for(int i=0;i<n;i++){
            char c=tolower(s[i]);
            for(int j=4;j>=1;j--){
                if(c==t[j-1]){
                    f[j]=(f[j]+f[j-1])%M;
                }
            }
        }
        cout<<f[4]<<"\n";
    }
}
int main(){
    //ios::sync_with_stdio(false),cin.tie(0);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}