简要题意

定义：如果一个 \(01\) 串是“反对称”的，当且仅当将其每一位取反后翻转，与原来的串相同。

给出一个长度为 \(n\) 的 \(01\) 序列。求其有多少个子串是“反对称”的。

\(1 \leq n \leq 5\times10^5\)

思路

经典的 Manacher 练习题。

考虑到“反对称”的定义与回文的定义很像。只是一个是两边的字符相同，一个是两边的字符异或和为 \(1\)。

于是我们可以修改 Manacher 模板来实现。

统计答案时，设 \(p_i\) 为以 \(i\) 为对称中心，我们求出来的最长循环半径长度。则其实际为 \(\lfloor p_i\div2\rfloor\)（去掉 # 的干扰）。累加起来即可。

注意本题几个坑点（感谢 这个帖子）：

• Manacher 构建新字符串时是 \(i=i+2\)。应为奇数长度的“反对称”串不存在（中心不存在，因为不存在一个数，使得其取反等于其本身）。但是可能会被 # 误导，从而被错误地计算。
• 十年 OI 一场空，不开 long long 见祖宗。

代码

#include <bits/stdc++.h>
using namespace std;

int n;
string str;

const int N = 2e6+5;

string pre(string s){
    if(s.size()==0) return "^$";
    string ret="^";
    for(int i=0;i<s.size();i++){ret+='#';ret+=s[i];}
    return ret+="#$";
}

int p[N];

bool XOR(char a,char b){
    return (a=='1'&&b=='0')||(a=='0'&&b=='1')||(a=='#'&&b=='#');
}

long long manacher(string str){
    int n=str.size(),c=0,r=0;
    long long ans=0;
    for(int i=1;i<n;i+=2){
        int j=(c<<1)-i;
        if(r>i) p[i]=min(r-i,p[j]);
        else {p[i]=0;}
        while(XOR(str[i+p[i]+1],str[i-p[i]-1])) p[i]++;
        if(i+p[i]>r){c=i;r=i+p[i];}
        ans+=p[i]>>1;
    }
    return ans;
}

int main(){
    cin>>n>>str;
    cout<<manacher(pre(str));
    return 0;
}