# 2452. 「POI2010」反对称 Antisymmetry

【题目描述】

对于一个 $0/1$ 字符串，如果将这个字符串 $0$ 和 $1$ 取反后，再将整个串反过来和原串一样，就称作「反对称」字符串。比如 $00001111$ 和 $010101$ 就是反对称的，而 $1001$就不是。

现在给出一个长度为 $n$ 的 $0/1$ 字符串，求它有多少个子串是反对称的，注意这里相同的子串出现在不同的位置会被重复计算。

【算法】

0\1取反和对称操作的前后顺序显然不影响，先考虑对称操作再考虑取反，于是可以发现子串长度显然是偶数而且关于对称轴0/1对称（一边为0则另一边为1）。

算法1： 枚举对称轴，二分+hash。时间复杂度$O(nlog(n))$。

算法2： manacher算法，$O(n)$的时间算出所有子串最长回文子串长度（此题改下判断条件就好）。

【代码】

#include <bits/stdc++.h>

#define ull unsigned long long

using namespace std;

int n;

ull ans;

int r[1001000];

char s[500100],c[1001000];

int main() {

    scanf("%d%s",&n,s+1);

    c[0]='$';

    for(int i=1;i<=n;i++) {

        c[2*i-1]='#';

        c[2*i]=s[i];

    }

    c[2*n+1]='#'; c[2*n+2]='$';

    int mx=0,po=0;

    for(int i=1;i<=2*n;i+=2) {

        if(mx>i) r[i]=min(mx-i,r[2*po-i]);

        else r[i]=1;

        while((c[i+r[i]]==c[i-r[i]]&&c[i+r[i]]=='#')||(c[i+r[i]]-'0'+c[i-r[i]]-'0'==1))

            r[i]++;

        if(i+r[i]>mx) mx=i+r[i],po=i;

        ans+=r[i]>>1;

    }

    printf("%lld\n",ans);

    return 0;

}