题目描述

难度分:$1400$

输入一个只包含a和b的字符串$s$，长度$[1,10^6]$。

每次操作，你需要从$s$中选择一个连续子串ab，把它替换成bba。

操作直到$s$中不含ab为止。

输出最小操作次数，模$10^9+7$。

输入样例$1$

ab

输出样例$1$

1

输入样例$2$

aab

输出样例$2$

3

算法

贪心

这种题目本来一看到就想用栈模拟的，但是一看结果竟然要对$10^9+7$取模，就能断定存在一定的数学规律。根据题目所给样例再造几个发现如下规律：

对于一个aaa...aab模式的串，左边有$x$个a，手玩一下可以发现最终会变成bbb...bbaaa..aa，一共操作$2^x-1$次，左边会变成$2^x$个b，右边还是$x$个a。

我们可以遍历$s$串，同时维护a的数量$x$，一旦遇到b，且前面a的数量大于零就开始结算操作数，把$2^x-1$累加到答案上。而此时a的数量是不会变的，因此我们遍历下一个字符继续这个过程即可。

复杂度分析

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int MOD = 1e9 + 7;

int fast_power(int a, int k) {
    int res = 1 % MOD;
    while(k) {
        if(k&1) res = (LL)res * a % MOD;
        a = (LL)a * a % MOD;
        k >>= 1;
    }
    return res;
}

int main() {
    string s;
    cin >> s;
    int n = s.size(), a = 0, ans = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == 'a') {
            a++;
        }else {
            ans = ((ans + fast_power(2, a)) % MOD - 1 + MOD) % MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}