Gym - 101350A Sherlock Bones（思维）

The great dog detective Sherlock Bones is on the verge of a new discovery. But for this problem, he needs the help of his most trusted advisor -you- to help him fetch the answer to this case.

He is given a string of zeros and ones and length N.

Let F(x, y) equal to the number of ones in the string between indices x and yinclusively.

Your task is to help Sherlock Bones find the number of ways to choose indices (i, j, k) such that i < j < k, s_j is equal to 1, and F(i, j) is equal to F(j, k).

Input

The first line of input is T – the number of test cases.

The first line of each test case is an integer N (3 ≤ N ≤ 2 × 10⁵).

The second line is a string of zeros and ones of length N.

Output

For each test case, output a line containing a single integer- the number of ways to choose indices (i, j, k).

Example

Input

Outpu2

3
7

题意：
给定01字符串，求有多少个三元组i,j,k满足i<j<k且F(i, j)=F(j, k).其中F（x,y）是字符串下标x到y的一的个数。
下标为j的一定要是1。
思路：
先处理一下0的数量分布。比如00110就是2,0,1
假设字符串以0为开头和结尾，那么字符串便可以表示为：
a,1,b,1,c,1,d,1,e,1,f
其中字母表示0的数量。
枚举j在哪一个1上，便可以得出以下式子、
ans=a*b+  b*c+a*d+  c*d+b*e+a*f+  d*e+c*f+  e*f;
可以看出，每一个字母其实就是要与之后奇数或偶数的后缀和相乘，乘积相加就是结果。
但是这样仍然不对，因为i可k还可以指向1.
于是我们把每个字母的值加上一个1，再进行计算即可。
然而这样还是有问题。
相邻的两个字母相乘时不需要+1，于是我们再用一个for循环处理一下即可。

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#define fuck(x) cout<<#x<<" = "<<x<<endl;

#define ls (t<<1)

#define rs ((t<<1)+1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = ;

const int inf = 2.1e9;

const ll Inf = ;

const int mod = ;

const double eps = 1e-;

const double pi = acos(-);

char s[maxn];

vector<ll>v;

ll sum[maxn];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--){int len;

        scanf("%d%s",&len,s);

        memset(sum,,sizeof(sum));

        v.clear();

        ll ans=;

        for(int i=;i<len;i++){

            if(s[i]==''){

                ans++;

            }

            else{

                v.push_back(ans);

                ans=;

            }

        }

        v.push_back(ans);

        int sz=v.size();

        for(int i=sz-;i>=;i--){

            sum[i]=v[i]+sum[i+];

        }

        ans=;

        for(int i=;i<sz;i++){

            ans+=v[i]*sum[i+];

        }

        for(int i=;i<sz-;i++){

            ans-=v[i]*v[i+]-(v[i]-)*(v[i+]-);

        }

        printf("%lld\n",ans);

    }

    return ;

}

秒客网

Gym - 101350A Sherlock Bones（思维）

相关文章