Codeforces Round #411 D. Minimum number of steps

题意

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.

解题思路

根据题意，转换规则如下：

ab→bba

abb→bbbba

abbb→bbbbbba

即对于任意一个 a ，与其直接相邻的连续 b 的个数将是其 replace 的次数，同时 b 的个数将翻倍。

同时可以想象，对于最终停止 replace 操作时的串的状态，必然是形如 bb...baa...a 。

故对于该问题，逆序处理该串，统计 b 的个数作为 cntb 。当找到一个 a 时，可以保证 cntb 个 b 必然与该 a 直接相连，对答案的贡献为 cntb 。同时 cntb 需倍乘。

代码

#include<bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; char s[1000010]; int main() { scanf(" %s",s); int len = strlen(s); long long cntb = 0, ans = 0; for(int i=len-1;i>=0;--i) { if(s[i] == 'a') { (ans += cntb) %= mod; (cntb *= 2) %= mod; } else { cntb++; } } printf("%I64d\n", ans%mod); }