题意
若一个由 01 01 01组成的字符串将 0 0 0和 1 1 1取反，并倒过来后与原字符串相同，则称为反对称字符串。现在给你一个长度为 n ( n ≤ 1 0 5 ) n(n \le 10^5) n(n≤105) 01 01 01组成的字符串，求它有多少个反对称子串。（两个子串只要起始位置不同或长度不同就算做两个子串，即使子串的内容相同）
样例
8
11001011
7
思路
朴素
先预处理出原字符串的 H a s h Hash Hash数组和原字符串 01 01 01取反并前后颠倒的 H a s h Hash Hash数组，然后枚举每个子串，判断两个 H a s h Hash Hash是否相等，计数。复杂度 O ( n 2 ) O(n^2) O(n2)，喜提TLE。
进阶
（此时我偷偷看了一下题目的标签，要用二分） 先考虑如何构造一个反对称字符串，如果没有“反”，那么就是回文串，很明显，是从中间开始，向两边扩展，对应位置的
01
01
01相同，例如：
01010
01010
01010和
11100111
11100111
11100111。但是要分成两种情况，奇数长度的字符串和偶数长度的字符串构造方法略有不同。可是有“反”，也就是说对应位置不是相同，而是相反。带到样例里算一下，比如说
001011
001011
001011，构造过程如下：
10
10
10 ->
0101
0101
0101 ->
001011
001011
001011。进一步发现，每一步都会构成一个反对称字符串，这就给二分提供了基础。
实现
可以枚举每个反对称子串中间两个位置的右边那个（这里需要注意一个细节，其实完全不用分两种情况，因为对应位置的字符不同，如果长度是奇数，中间的字符不可能和自己不同，所以长度只能是偶数），用二分找到最大的反对称字符串长度（实际的长度是 2 ⋅ m i d 2·mid 2⋅mid，这里枚举半边的长度），判断时看 i − m i d i-mid i−mid到 i + m i d − 1 i+mid-1 i+mid−1的子串是否是反对称串，如果是，就可以继续扩大长度判断，如果不是，由于中心确定，已经发现对应位置上的字符相同，不符合要求，再向两边扩大长度也不会成为反对称串，所以缩小长度。
代码
（本人为了保险，写了两个哈希表，其实一个也能过）
#include<bits/stdc++.h>
using namespace std;
#define mod1 1000000007
#define mod2 1000000009
#define mul 2
int n,a[500005];
long long h1[500005],h2[500005],g1[500005],g2[500005];
//h是原字符串，g是取反翻转后的
long long m1[500005],m2[500005],ans;
char s[500005];
int main(){
scanf("%d%s",&n,s+1);
m1[0]=m2[0]=1;
for(int i=1;i<=n;i++) m1[i]=m1[i-1]*mul%mod1;
for(int i=1;i<=n;i++) m2[i]=m2[i-1]*mul%mod2;
for(int i=1;i<=n;i++) h1[i]=(h1[i-1]*mul%mod1+(s[i]=='1'))%mod1;
for(int i=1;i<=n;i++) h2[i]=(h2[i-1]*mul%mod2+(s[i]=='1'))%mod2;
for(int i=n;i>=1;i--) g1[i]=(g1[i+1]*mul%mod1+(s[i]=='0'))%mod1;
for(int i=n;i>=1;i--) g2[i]=(g2[i+1]*mul%mod2+(s[i]=='0'))%mod2;
for(int i=1;i<=n;i++){
int l=1,r=min(i-1,n-i+1),flag=0;
while(l<=r){
int mid=(l+r)/2;
int t1=(h1[i+mid-1]-h1[i-mid-1]*m1[2*mid]%mod1+mod1)%mod1,
t2=(h2[i+mid-1]-h2[i-mid-1]*m2[2*mid]%mod2+mod2)%mod2,
tt1=(g1[i-mid]-g1[i+mid]*m1[2*mid]%mod1+mod1)%mod1,
tt2=(g2[i-mid]-g2[i+mid]*m2[2*mid]%mod2+mod2)%mod2;
if(t1==tt1&&t2==tt2) l=mid+1,flag=1;
else r=mid-1;
}
ans+=r;
}
printf("%lld\n",ans);
return 0;
}
附赠如何见到祖宗的指南：
