Description

现在我们有一个由01组成的字符串。我们需要在上面做一些操作。每次我们都选一个“01”子串，把他替换成110。如果找不到“01”子串，那么操作结束。请输出总共进行了多少次操作，结果请mod 1e9+7。

 

Ps：“01”子串必须是相邻的0和1，字符串中只包含0和1。

 

 

Input

首先一个T，代表接下来有T行。

接下来的T行，每行一个字符串str

（1<= T <= 200, 所有字符串长度和 len <= 2e7）

Output

 对于每个字符串，输出相应操作数。

 

Sample Input

2
01
001

Sample Output

1
3

HINT

 

对于第二个字符串：

 

001 -> 0110 -> 11010 -> 111100

C++版本一

题解：

多模拟几个字符串的操作可以发现最后都会变成类似11111110000000的形式，即所有的1转移到左边，0转移到右边，且0在转移到右边的过程中个数不变。

对于01需要1（2^1-1）次，001需要3（2^2-1）次, 0001需要7（2^3-1）次，即对于每个1，如果它前面有N个0，则这N个0跳过这个1需要（2^N-1）次。

我们就可以直接遍历字符串，然后统计0的个数cnt，碰到1则将（2^cnt-1）加到答案中。

这里计算2^cnt-1不能用快速幂，直接用前面的*2即可，否则可能会超时。

#include<cstdio>
#define LL long long
LL mod = 1e9+7;
const int maxn = 1e6+10;
 
char str[maxn];
 
int main() {
    //freopen("data1.in","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%s",str);
        LL ans = 0,ba = 1;
        for(int i = 0;str[i];i++) {
            if(str[i] == '0') ba = ba*2%mod;
            else ans = (ans+ba-1)%mod;
        }
        printf("%lld\n",ans);
    }
}

 C++版本二

题解：

快速幂

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int N=2e7+100;
const int M=1e9+7;
int t,n,m;
char a[N];
int p[N];
void pow2(){
    ll tmp=1;
    p[0]=tmp;
    for(int i=1;i<=N;i++){
        tmp*=2;
        tmp%=M;
        p[i]=tmp;
    }
}
int main()
{
    scanf("%d",&n);
    pow2();
    while(n--){
        scanf("%s",a);
        int len=strlen(a);
        int cnt=0;
        ll ans=0;
        for(int i=0;i<len;i++){
            if(a[i]=='0')
                cnt++;
            else{
                ans+=(p[cnt]-1);
                ans%=M;
            }
        }
        cout << ans << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}