Description：

给一个 $01$ 串，问他有几个子串取反倒置后和原子串相同。

$1\le n \le 1000000$

Solution：

$\text{manacher}$ 的奇怪应用，按照题解的说法，设#对应#， $0$ 对应 $1$ ， $1$ 对应 $0$ ，然后做 $\text{manacher}$ ，求出以每个位置为中心的对应最长回文半径，这个只要在扩展时判断对应相等即可，然后把所有偶数长度的回文串统计一下，写完交了只有 $10$ 分，原因是因为会有这样一种情况：

s[i]: # 1 # 1 # 0 # 0 #

h[i]: 1 2 1 4 5 4 1 2 1

为什么会出现这种情况呢，因为第 $3$ 位的 $0$ 对应过去之后原来的奇偶性改变对应的就不再对应了，而这是因为我们把奇数长度的回文串也用在了更新 $maxr$ 时，而这样会破坏对应关系，所以只要跳过所有 $i\%2=0$ 的时候就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

map<char,char> to;

char S[MAXN],s[MAXN];

int h[MAXN];

int main()

{

    scanf("%d",&n);

    scanf("%s",S + 1);

    to['0'] = '1';to['1'] = '0';to['#'] = '#';

    int tot = 0;s[++tot] = '#';

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

    {

        s[++tot] = S[i];s[++tot] = '#';

    }

    int pos = 1,maxr = 1;

    long long ans = 0;

    for(int i = 1;i <= tot;i += 2)

    {

        if(maxr > i)h[i] = min(h[pos * 2 - i],maxr - i + 1);

        else h[i] = 1;

        while(i - h[i] >= 1 && i + h[i] <= tot && s[i + h[i]] == to[s[i - h[i]]])++h[i];

        if(i + h[i] - 1 > maxr)

        {

            maxr = i + h[i] - 1;

            pos = i;

        }

        ans += h[i] / 2;

    }

    cout << ans << endl;

    return 0;

}