D. Minimum number of steps time limit per test
1 second memory limit per test
256 megabytes input
standard input output
standard output We have a string of letters 'a' and 'b'. We want to perform some operations on it. On each step we choose one of substrings "ab" in the string and replace it with the string "bba". If we have no "ab" as a substring, our job is done. Print the minimum number of steps we should perform to make our job done modulo 109?+?7.
The string "ab" appears as a substring if there is a letter 'b' right after the letter 'a' somewhere in the string.
Input The first line contains the initial string consisting of letters 'a' and 'b' only with length from 1 to 106.
Output Print the minimum number of steps modulo 109?+?7.
Examples input
ab
output
1
input
aab
output
3
Note The first example: "ab" ?→? "bba".
The second example: "aab" ?→? "abba" ?→? "bbaba" ?→? "bbbbaa".
题目大意：
给你一个只包含a，b两种字母的字符串，如果有一个连续子串为ab.那么就可以将其变成bba.让你计算这个给出的字符串在操作了多少次之后不能再进行操作了。
思路：
最终字符串一定会变成bbbbbbb........aaaa..............
所以前边的a是要累加起来的。
我们观察到ab答案是1
aab答案是3.
aaab答案是7.
那么一个b前边有n个a，那么这个b会贡献2^n-1次操作。
abab答案是4 =1 + 3
那么对应累加前边的a.一旦遇到b就加上2^n-1即可。
Ac代码：
#include
#include
using namespace std;
#define ll __int64
#define mod 1000000007
char a[1000800];
ll poww(ll a,ll b)
{
ll tmp=a%mod;
ll ans=1;
ll n=b;
while(n)
{
if(n%2==1)
{
ans=(ans*tmp)%mod;
n-=1;
}
else
{
tmp=(tmp*tmp)%mod;
n/=2;
}
}
return ans;
}
int main()
{
while(~scanf("%s",a))
{
ll cnt=0;
ll output=0;
ll n=strlen(a);
for(ll i=0;
i【思维|Codeforces Round #411(Div. 2)D. Minimum number of steps【思维递推+快速幂】】
推荐阅读
- 每日一题|每日一题-解码（第十一届蓝桥杯）（简单思维）
- codeforces|Codeforces Round #665 (Div. 2) A. Distance and Axis(思维，数学)
- codeforces|Codeforces Global Round 10 C. Omkar and Waterslide(思维)
- codeforces|Codeforces Global Round 10 D. Omkar and Bed Wars(思维，分块)
- codeforces|Codeforces Round #643 (Div. 2) D. Game With Array (思维，贪心)
- codeforces|Codeforces Round #648 (Div. 2) C. Rotation Matching(思维)
- CodeForces - 245C Game with Coins
- Codeforces Round #643 (Div. 2) C. Count Triangles 题解（思维）
- #|C. Choosing flowers（枚举+思维+二分）
- #|A. Distance and Axis（思维） Codeforces Round #665 (Div. 2)