点击打开链接
题意:给出string 只包含字符'a','b',长度<=1e6,每次把ab变成bba问变换次数? 简单观察 若有abbb ->bbabb bbbbbba a后面有多少个b该'ab'就变化多少次,并且b的个数增加为原先两倍. 从后往前 碰到b累加,碰到a更新答案并把b的数量翻倍
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+20;
const ll mod=1e9+7;
char s[N];
int main()
{
while(scanf("%s",s+1)!=EOF)
{
int n=strlen(s+1);
ll num=0,ans=0;//b的数量
for(int i=n;i>=1;i--)
{
if(s[i]=='b')
num++;
else
{
//碰到a ab->bba后面有多少个b就翻多少倍
ans=(ans+num)%mod;
num=(num*2)%mod;
}
}
cout<<ans<<endl;
}
return 0;
}
