jennie

求形如abababababa的子序列数量？

$fi=sum{j=1}^{i-1}f_jquad a_i=b且 a_j=a$

$fi=sum{j=1}^{i-1}f_j+1quad a_i=a且 a_j=b$

顺便可以发现，以b结尾不能作为答案

所以说可以优化成没有递推

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#define int long long
using namespace std;
int mod=1000000007;
int now;
int ans;
string s;
signed main(){
    cin>>s;
    int l=s.length();
    for(int i=0;i<l;++i){
        if(s[i]=='a'){
            ans=(ans+1+now)%mod;
        }
        if(s[i]=='b'){
            now=ans;
        }
    }
    cout<<ans;
    return 0;
}