题目大意:
给定原字符序列
找出其中所有子序列满足
1.序列内字符都为a
2.若有两个以上的字符 则相邻两个字符在原序列中两者之间存在字符b
的数量
将整个字符序列用b分开
此时再得到每个b之间a的数量
即 abbgaaba 得到 v[] = { 1 0 2 1 }
此时假设到第 i-1 段 已得到在第 i-1 段内的所有方案数为 ans （长度为1、2、3、... 、i-1）
则在第 i 段时 可由前一段的方案数 和 当前段数量 组合得到ans*v[ i ] （长度为2、3、4、... 、i）
此时第 i 段还可以作为长度为1的方案 即ans=ans*v[ i ] + v[ i ]=(ans+1)*v[ i ]
那么递推即可得到所有方案数
#include <bits/stdc++.h> #define LL long long #define INF 0x3f3f3f3f using namespace std; const int N=1e5+5; const int mod=1e9+7; char ch[N]; LL v[N]; int main() { while(~scanf("%s",ch)) { int len=strlen(ch); memset(v,0,sizeof(v)); v[0]=1LL; int i=0, c=1; while(i<len) { LL m=0LL; while(i<len && ch[i]!=‘b‘) { if(ch[i]==‘a‘) m++; i++; } v[c++]=m; i++; } LL ans=0LL; for(int j=1;j<=c;j++) ans=(ans+(ans+1LL)*v[j]%mod)%mod; printf("%I64d\n",ans); } return 0; }
Codeforces Round #526 C - The Fair Nut and String /// 组合递推
原文：https://www.cnblogs.com/zquzjx/p/10104289.html
