C. The Fair Nut and String 递推分段形dp

题意

给出一个字符串选择一个序列\({p_1,p_2...p_k}\)使得
对于任意一个\(p_i\) , \(s[p_i]==a\)
对于任意一个\(p_{i}<j<p_{i+1}\)来说 \({\exists}s[p_j]==b\)

思路

所以我们可以得知 我们需要选择一系列a 使得a和a之间只能是b
那么我们就可以对a进行分段处理
例如aaaabaaaa 右面与前面组合 只能选择后面一大串a的前缀和前面一大串a的后缀组合才合法
也就是一共有 num[1]*num[2]中组合 其中num[i] 表示第i段有多少个a
而如果多段组合的话 第三段既可以和第二段组合 也可以和第二段+第一段组合
第二段+第一段就是 在算第三段之前的合法选择数，而第三段和第二段 同第一段和第二段的算法相同
所以递推求解即可 而分段的时候如果字母不是b 直接忽略就行了（因为只是\({\exists}s[p_j]==b）\)所以不会干扰a和a的组合可以忽略，相当于归到一段a中但是这一段a的数量不变
ps:记得开long long

#include<bits/stdc++.h>
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
#define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 
#define F first 
#define S second
#define pii pair<int ,int >
#define mkp make_pair
#define pb push_back
#define arr(zzz) array<ll,zzz>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
int n,m,y;
const int mod=1e9+7;
char s[maxn];
int main(){
    
    scanf("%s",s+1);
    int len=strlen(s+1);
    long long ans=0;
    for(int i=1;i<=len;i++){
        if(s[i]=='a')ans++;
    }
    ll flag=0;
    ll tmp=0;
    int cnt=0;
    ll x=0;
    ll fixsum=0;
    ll lastsum=0;
    int ok=0;
    for(int i=1;i<=len;i++){
        if(s[i]=='a'){
            flag++;
        }
        else if(s[i]=='b'){
            if(flag){
                cnt++;
            tmp+=flag*fixsum;
            tmp%=mod;
            //ll zzzz=lastsum;
            //lastsum=tmp;
            tmp+=lastsum*flag;
            tmp%=mod;
            lastsum=tmp;
            fixsum+=flag;
            fixsum%=mod;
            flag=0;
            }
        }
        if(s[i]=='b')ok=0;
        else if(s[i]=='a')ok=1;
    }
    if(ok){
                cnt++;
            tmp+=flag*fixsum;
            tmp%=mod;
            //ll zzzz=lastsum;
            //lastsum=tmp;
            tmp+=lastsum*flag;
            tmp%=mod;
            lastsum=tmp;
            fixsum+=flag;
            fixsum%=mod;
            flag=0;
    }
    if(cnt>=2)ans+=tmp;
    ans%=mod;
    cout<<ans<<endl;
    return 0;
}

C. The Fair Nut and String 递推分段形dp

原文：https://www.cnblogs.com/ttttttttrx/p/10800062.html