[Poi2010]Antisymmetry

$Description$

对于一个 $01$ 字符串，如果将这个字符串 $0$ 和 $1$ 取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如 $00001111$ 和 $010101$ 就是反对称的， $1001$ 就不是。
现在给出一个长度为 $N$ 的 $01$ 字符串，求它有多少个子串是反对称的。

$Input$

第一行一个正整数 $N (N <= 500,000)$ 。第二行一个长度为 $N$ 的 $01$ 字符串。

$Output$

一个正整数，表示反对称子串的个数。

$Sample Input$

8

11001011

$Sample Output$

$hint$

$7$ 个反对称子串分别是： $01$ (出现两次), $10$ (出现两次), $0101$ , $1100$ 和 $001011$

思路：第一眼看到这个题目毫无头绪，只会暴力判断，但是，仔细观察后，如果一个子串 $01$ 翻转后是一个回文串，那就代表这个子串是符合条件的，于是我们自然而然的就想到了 $Manacher$ 算法。
考虑如何使用 $Manacher$ 算法。
可以发现，原题的关键就是要使 $'0'$ 和 $'1'$ 、'#'和'#'匹配('#'是 $Manacher$ 要用的符合，视个人情况而定吧)，而其他都不匹配。显然，使用异或操作是可行的，但是这样'#'的值就不好定义，因为无论'#'定义成什么，('#')^('#')=0。
考虑 $Manacher$ 算法更新 $p$ (回文半径)是如何更新的，就是能扩展的就扩展，分类讨论一下，然后在这个题目当中只要 $01$ 匹配就可以了，那我们暴力扩展的时候直接判一下就可以了。
另外，在 $Manacher$ 的时候，可以只考虑偶数位字符，因为奇数个字符组成的子串不可能反对称。

然后这个题就做完了。。

当然这个题目不只可以用 $Manacher$ ，还可以二分+哈希搞一下，这里就不展开说了，有兴趣的同学
可以 ~~上网搜一下~~(自己想一下)，我才不会说是因为我不会呢。。。

剩下的是我简洁(逃……)的代码：

#include<cstdio>
#include<algorithm>
#define int long long
#define maxn 1000007
using namespace std;
char s[maxn>>1],str[maxn];
int n,p[maxn],ans;
int init() {
  str[0]='@',str[1]='#';
  int p=1;
  for(int i=1;i<=n;++i) str[++p]=s[i],str[++p]='#';
  str[p+1]='@';
  return p;
}
void Manacher() {
  int maxx=0,id=0,len=init();
  for(int i=1;i<=len;++++i) {
    if(i<maxx) p[i]=min(maxx-i,p[id*2-i]);
    else p[i]=1;
    while((str[i+p[i]]=='#'&&str[i-p[i]]=='#')||(str[i+p[i]]-'0'+str[i-p[i]]-'0'==1)) ++p[i];
    if(maxx<i+p[i]) maxx=i+p[i],id=i;
  }
}
signed main() {
  scanf("%d%s",&n,s+1);
  Manacher();
  n<<=1;
  ++n;
  for(int i=1;i<=n;++++i) ans+=p[i]>>1;
  printf("%lld\n",ans);
  return 0;
}