给一个 只包含 ‘a’,’b’的string 。现有 opeartion 将 string 中的 substring 中的“ab”,替换成“bba”。求 将所有 子串替换换完的最小操作次数。
ab->bba; aab-> a bba-> bba ba-> bb bbaa aaab-> a abba->a bbaba->a bbbbaa-> bb a bbba-> bb bba bbaa ->bbbb bba baa -> bbbb bb bba aa 。 从中可以发现：就是把 前面 所有 a 移到 该个 b 之后，如果前面有 n个a,就要移动（1+2+4+……+2^(n-1) ）次。
#include <bits\stdc++.h> using namespace std; const int maxn = 1e5+50; #define FCIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); const int MAXINT = 0x7fffffff; const int MININT = 0x80000000; const int mod = 1e9+7; typedef long long LL; char s[maxn*10]; int my_pow(int a,int b){ LL ans = 1, q = a; while(b){ if(b&1){ ans *= q; ans%=mod; } q*=q; q%=mod; b>>=1; } return ans; } int main(){ scanf("%s",s); long long ans = 0; int len =strlen(s); int numa = 0, numb = 0; for(int i=0;i<len;i++){ if(s[i]=='a') numa+=1; if(s[i]=='b'){ ans += my_pow(2,numa)-1; ans %= mod; } } printf("%lld\n",ans); return 0; }