题意：给你一个长度为\(n\)的\(01\)串，求它的非空并在异或意义下回文的子串数。
这里我们介绍马拉车的扩展：
引入\(to\)数组，表示每个字符与哪个字符匹配。
例如，在模板题中，有\(\forall c \in ['a','z'],to_c=c\)。
而在这道题中，有\(to_{'1'}='0',to_{'0'}='1'\)
并且我们令\(to[\)#\(]=[\)#\(]\)
然后就可以匹配了。
注意！！这个时候初始回文串长度应为\(0\)，因为自己不一定与自己相配。
即：
rad[i]=(i<Rpos)?min(Rpos-i,rad[Centre*2-i]):0;
最后是\(0\)不是\(1\)。
另，统计答案时应是：
Ans+=(rad[i]>>1);
因为加入了辅助字符 # ，所以数量要减半。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int S,rad[1001000],Rpos,Centre,Ans;
char s[1001000],to[129];
void getln(){
char c=getchar();
to['0']='1',to['1']='0',to['$']='$';
s[0]='$',S=1;
while(c!='0'&&c!='1')c=getchar();
while(c=='0'||c=='1')s[S++]=c,s[S++]='$',c=getchar();
s[S]='\0';
}
void Manacher(){
Rpos=Centre=-1;
for(int i=0;i<S;i++){
rad[i]=(i<Rpos)?min(Rpos-i,rad[Centre*2-i]):0;
while(i-rad[i]>=0&&i+rad[i]<S)if(to[s[i-rad[i]]]==s[i+rad[i]])rad[i]++;else break;
if(i+rad[i]>Rpos)Rpos=i+rad[i],Centre=i;
Ans+=(rad[i]>>1);
}
}
signed main(){
scanf("%lld",&S);
getln();
Manacher();
printf("%lld",Ans);
return 0;
}