题意描述

　　　　一句话描述：对于一个0/1序列，求出其中异或意义下回文的子串数量。

题解

　　我们可以看出，这个其实是一个对于异或意义下的回文子串数量的统计，什么是异或意义下呢？平常，我们对回文的定义是，对于任意$i$,$S[i]=S[n-i+1]$，而我们把相等改为异或操作，那么，当且仅当$1$与$0$相匹配时，返回值为$1$ 也就是 “真”。

　　那么，我们可以尝试使用Manache算法来解决。当然，编程时，我们并不必真的去把0/1序列转换为数字序列，进行异或操作，这样会给自己增加一波常数（迷），我们构造一个to数组，$to[x]$数组的定义为 对于字符$x$ 我们允许匹配的对应字符，显然，$to['0']='1'$,$to['1']='0'$，特别的$to['\#']='\#'$ $to['\$']='\$'$。（此处'#'与'$'是Manache算法的分隔字符与防止溢出字符，可以自定义）。

　　对于Manache算法有任何不了解的地方，可以戳!!!这里!!!，又看不懂的地方，也可以联系文文

最后推一波自己博客（逃

　　对于代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
const int maxn = 1000010;
typedef unsigned long long ull;
char SS1[maxn],S[maxn],to[500];
int n,len[maxn],tot=1;
int main() {
	scanf("%d%s",&n,SS1+1);S[0]='$',S[1]='#';
	for(register int i=1;i<=n;++i) S[++tot]=SS1[i],S[++tot]='#';
	to['1']='0',to['0']='1',to['#']='#',to['$']='$';
	int pos=1,mx=1;ull ans=0;
	for(register int i=1;i<=tot;i+=2) {
		len[i]=(i<mx?std::min(mx-i,len[(pos<<1)-i]):1);
		while(S[i+len[i]]==to[S[i-len[i]]]) len[i]++;
		if(len[i]+i>mx) {
			mx=len[i]+i;pos=i;
		}
		ans+=len[i]>>1;
	}
	printf("%llu\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=510000;
char a[N], s1[2*N], s2[2*N];
int d[2*N], n;
void get_d()
{
    s1[0]='$'; s1[1]='#';
    for(int i=1; i<=n; i++) {
        s1[2*i] = a[i];
        s2[2*i] = a[i] ^ 1;
        s1[2*i+1] = s2[2*i+1] = '#';
    }
    n = 2*n + 1;
    memset(d, 0, sizeof(d)); d[1] = 1;
    for(int i=2, L=1, R=1; i<=n; i++) {
        if(i <= R) d[i] = min(d[R - i + L], R - i + 1);
        while(s1[i - d[i]] == s2[i + d[i]]) d[i]++;
        if(i + d[i] - 1 > R) {
            L = i - d[i] + 1;
            R = i + d[i] - 1;
        }
    }
}
int main()
{
    scanf("%d%s", &n, a + 1);
    get_d();
    long long ans = 0;
    for(int i=1; i<=n; i++) ans += (d[i] - 1)/2;
    printf("%lld\n", ans);
    return 0;
}