Gym - 101350A Sherlock Bones（思维）-白红宇

Gym - 101350A Sherlock Bones（思维）

阅读量：4987 次

发布时间：2019-06-12

本文共 1467 字，大约阅读时间需要 4 分钟。

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

3 5 01010 6 101001 7 1101011

Outpu2

3 7 题意： 给定01字符串，求有多少个三元组i,j,k满足i

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define fuck(x) cout<<#x<<" = "<
                   
                    <
                    
                     v;ll sum[maxn];int main(){ int T; scanf("%d",&T); while(T--){ int len; scanf("%d%s",&len,s); memset(sum,0,sizeof(sum)); v.clear(); ll ans=1; for(int i=0;i
                     
                      =0;i--){ sum[i]=v[i]+sum[i+2]; } ans=0; for(int i=0;i

View Code

转载于:https://www.cnblogs.com/ZGQblogs/p/10661616.html

你可能感兴趣的文章