【Codeforces Round #411 (Div. 1)】Codeforces 804B Minimum number of steps

显然，步数多少和操作顺序是没有关系的。因此可以从前往后扫描一遍。因为一旦出现ab就会被消除，因此所有出现过的a都会在当前序列末尾。所以只需要维护当前有几个a，遇到b的时候统计一下答案。也很容易发现如果有 x 个a，那么需要进行2x−1次操作。

#include<cstdio> #include<cstring> #define LL long long int n,p=1000000007; char s[2000010]; LL pow(LL b,int k) { LL ret=1; for (;k;k>>=1,b=b*b%p) if (k&1) ret=ret*b%p; return ret; } int main() { LL ans=0; int cnt=0; scanf("%s",s+1); n=strlen(s+1); for (int i=1;i<=n;i++) if (s[i]=='a') cnt++; else ans=(ans+pow(2LL,cnt)-1)%p; printf("%I64d\n",ans); }