参考博客：https://blog.csdn.net/lengqiu2015/article/details/76855681#reply
题意
给出一个长度为n的01串 我们定义F(x,y)是区间[x,y]内1的数量 请你计算有多少三元组（i,j,k）满足i<j<k，s[j]是1而且F[i,j]等于F[j,k] n<=200000
分析
一开始一直在想怎么枚举j然后计算方案数，发现这样我只能写O(N^2),GG。
原来可以把题目转化一下，问这个串内有多少区间内有奇数个1（单独一个1或者1000或者0001这一类的都属于非法的）。
然后可以用dp来解决（好像也可以不用dp？）
dp[i][0]是以i为结尾的区间含有奇数个1的有多少
dp[i][1]是以i为结尾的区间含有偶数个1的有多少
那么转移就比较好想了：
如果i是1，那么dp[i][1]=dp[i-1][0],dp[i][0]=dp[i-1][1]+1(奇数变偶数，偶数变奇数)
如果i是0，那么dp[i][1]=dp[i-1][1],dp[i][0]=dp[i-1][0]+1
这样把所有的dp[i][0]加起来，再减掉非法的区间就可以了~
这个题要开long long。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
const int maxn=+;
char a[maxn];
long long dp[maxn][]; int n,T;
long long ans; int main(){
scanf("%d",&T);
for(int t=;t<=T;t++){
scanf("%d",&n);
scanf("%s",a+);
ans=;
memset(dp,,sizeof(dp));
if(a[]==''){
dp[][]=;
dp[][]=;
}
if(a[]==''){
dp[][]=;
dp[][]=;
}
for(int i=;i<=n;i++){
if(a[i]==''){
dp[i][]=dp[i-][]+;
dp[i][]=dp[i-][];
}else if(a[i]==''){
dp[i][]=dp[i-][];
dp[i][]=dp[i-][]+;
}
}
for(int i=;i<=n;i++){
ans+=dp[i][];
}
//下面去掉10000
long long res=,all=; for(int i=n;i>=;i--){
if(a[i]==''){
all+=res;
res=;
}
else
res++;
}
ans-=all;
//下面去掉00001
res=,all=;
for(int i=;i<=n;i++){
if(a[i]==''){
all+=res;
res=;
}
else
res++;
}
ans-=all;
cout<<ans<<endl;
}
return ;
}