Antisymmetry

水题？？？

二分+哈希：对于每两个字符中间的空隙二分左右的长度，判断条件是左边的异或后的字符串与右边的没异或的字符串相不相等。

不是水题。。。

manacher：方法很简单，就是 \(1\) 对应 \(0\)，\(0\) 对应 \(1\) 直接硬跑。

至于为什么对：我们设在回文串中两个以对称轴对称的位置的两个位置 \(i, j\) 且 \(i < j\)，则在大回文串里的以 \(i\)，\(j\) 为对称轴的回文串长度至少相等。

此题也是同理，因为翻转 \(0,1\) 并不会改变回文的性质，所以 \(i，j\) 的回文串并不会影响，所以能直接跑。

对了，注意开 long long。

#include <bits/stdc++.h>

int N;
char string[510000];

class Manacher {
public:
    char str[1010000], to[300];
    int n, pail[1010000];

    void Change(int len, char *temp) {
        to['0'] = '1';
        to['1'] = '0';
        to['#'] = '#';
        to['~'] = '~';

        str[0] = '~';
        str[++ n] = '#';
        for (int i = 1; i <= len; ++ i) {
            str[++ n] = temp[i];
            str[++ n] = '#';
        } 
    }

    void manacher() {
        for (int pos = 1, maxR = 0, mid = 0; pos <= n; ++ pos) {
            if (pos <= maxR)
                pail[pos] = std::min(pail[(mid << 1) - pos], maxR - pos + 1);
            while (str[pos - pail[pos]] == to[str[pos + pail[pos]]])
                pail[pos] ++;
            if (pos + pail[pos] - 1 > maxR) {
                maxR = pos + pail[pos] - 1;
                mid = pos;
            }
        }
    }
}manacher;

long long answer;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N >> (string + 1);
    manacher.Change(N, string);
    manacher.manacher();

    for (int i = 1; i <= manacher.n; ++ i) {
        if (manacher.str[i] == '#') {
            answer += (manacher.pail[i] - 1) / 2ll;
        }
    }

    std::cout << answer << '\n';
    return 0;
}