Codeforces 1084C

给你一个字符串，找出有多少个字串，使得字串的前后都是’a’，并且中间有一个‘b’,只有一个’a’也符合条件。
由于字符串中可能有别的字符，需要预处理把除了’a‘和’b’之外的字符都剔除，然后只剩下一个‘a’、‘b’序列，字符串中分成了几段’a’,这些’a’和属于不同部分的’a’对答案有贡献。
具体有多少贡献呢，举个例子，如果有三段，分别有1，2，4个‘a’,
设a,b,c,d,e,f,g分别表示这7个’a’,第一段是a,第二段是b和c，第三段是defg
i = 1时，只有[a]满足，
i = 2时，可知[a],[a,b],[a,c],[b],[c]5（1+12+2）个，
分析这5个如何得来：[a]是原来就有的，[b],[c]用cnt[i]表示，而[a,b]和[a,c]可以这么想，是前面的各种排列（就一种[a])的后面分别加了b和c
i = 3,有 增加的有[a,d],[a,e]…[a,g],[a,b,d]…[a,b,g] … [c,d],…[c,g],[d]…[g],一共是54 + 4个，可以知道后一项是完全建立在前一项的基础之上的。答案就出来了。

#include using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
char s[101010],s2[101010];
LL cnt[101010],len,num,ans,len1,tot;
int main(){cin>>s2;len = strlen(s2);for(int i = 0;i=len1) break;if(!i || s[i-1] == 'b') cnt[++num]++;else cnt[num]++;}for(int i = 1;i<=num;i++){ans = (ans + ( ans + 1 ) * cnt[i] % mod) %mod;} cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！