9.16深信服笔试题3：最长连续1串子串数，运行时间44ms

#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;

int main(){
    
    int n, maxlength = 0, left = 0, right = 0;
    vector<int> start; 
    string s;
    cin>>n>>s;
    
    while(right < n){
        while(right < n && s[right] == '0')right ++;
        if(right == n)break;
        left = right;
        while (right < n && s[right] == '1')right ++;

        int tmp = right-left;
        if(tmp == maxlength)start.push_back(left);
        else if(tmp > maxlength){
            maxlength = tmp;
            start.clear();
            start.push_back(left);
        }
    }
    if(start.empty()){cout<<0; return 0;}

    int size = start.size(), prev = -1;
    long long  ans = 0, sum = 0, squareSum = 0;

    for(int i = 0; i < size; i++){
        int tmp = start[i];
        start[i] = start[i] - prev;
        prev = tmp;
    }
    start.push_back(n + 1 - prev - maxlength);
    
    //巧妙计算
    for(auto &i : start){
        sum += i;
        squareSum = (squareSum + ((long long)i * i))%MOD;
    }
    ans = sum * sum - squareSum;
    ans = (ans < 0)? (ans + MOD)%MOD : ans%MOD;
    if(ans % 2)ans = (ans + MOD)/2;
    else ans /= 2;
    //非巧妙计算会超时，代码如下：
    /*
    for(int i = 1; i <= size; i++){
        for(int j = 0; j < size+1-i; j++){
            ans += start[j] * start[j+i];
            ans %= MOD;
        }
    }
    */
    cout<<ans;
    return 0;
}