参考博客：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。
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 const int maxn=200000+10; 8 char a[maxn]; 9 long long dp[maxn][2];10 11 int n,T;12 long long ans;13 14 int main(){15 scanf("%d",&T);16 for(int t=1;t<=T;t++){17 scanf("%d",&n);18 scanf("%s",a+1);19 ans=0;20 memset(dp,0,sizeof(dp));21 if(a[1]=='1'){22 dp[1][0]=1;23 dp[1][1]=0;24 }25 if(a[1]=='0'){26 dp[1][1]=1;27 dp[1][0]=0;28 }29 for(int i=2;i<=n;i++){30 if(a[i]=='1'){31 dp[i][0]=dp[i-1][1]+1;32 dp[i][1]=dp[i-1][0];33 }else if(a[i]=='0'){34 dp[i][0]=dp[i-1][0];35 dp[i][1]=dp[i-1][1]+1;36 }37 }38 for(int i=1;i<=n;i++){39 ans+=dp[i][0];40 }41 //下面去掉1000042 long long res=1,all=0;43 44 for(int i=n;i>=1;i--){45 if(a[i]=='1'){46 all+=res;47 res=1;48 }49 else50 res++;51 }52 ans-=all;53 //下面去掉0000154 res=0,all=0;55 for(int i=1;i<=n;i++){56 if(a[i]=='1'){57 all+=res;58 res=0;59 }60 else61 res++;62 }63 ans-=all;64 cout< <