题目分析

这是一个关于反对称子串计数的问题。反对称字符串的定义是：将字符串中的0和1取反后，再反转整个字符串，结果与原字符串相同。

反对称字符串的性质

对于字符串 $s$，设其反对称操作为 $f(s)$：

• 将0变为1，1变为0
• 然后反转字符串

那么 $s$ 是反对称的当且仅当 $s = f(s)$。

重要观察：

• 反对称字符串的长度必须是偶数（因为反转后要与原串相同）
• 对于位置 $i$ 和 $j$（$i < j$），如果子串 $s[i..j]$ 是反对称的，那么必须有： $s[i] \neq s[j], s[i+1] \neq s[j-1], ..., s[\frac{i+j-1}{2}] \neq s[\frac{i+j+1}{2}]$

算法思路

这个问题可以转化为：找到所有长度为偶数的子串，使得对于每一对对称位置 $(i, j)$，都有 $s[i] \neq s[j]$。

Manacher算法的变种：

1. 构建两个新字符串：

   • t1：原字符串，字符间插入#
   • t2：原字符串取反，字符间插入#

2. 对这两个字符串运行Manacher算法，找出它们的最长公共子串

3. 对于每个#位置（对应原字符串的间隙），计算以该位置为中心的反对称子串数量

关键实现细节

• 反对称子串必须跨越中心对称
• 对于中心在#的回文半径 $hw[i]$，能形成的反对称子串数量为 $(hw[i]-1)/2$
• 只统计中心在#的情况，这对应原字符串中长度为偶数的子串

代码实现

#include <bits/stdc++.h>
#define N 500010
#define int long long
using namespace std;

int n;
string s, t1, t2;
int maxright, hw[2 * N];
int ans;

void manacher() {
    int mid = 0, maxright = -1;
    
    for (int i = 1; i <= n * 2 + 1; i++) {
        // 利用对称性优化
        if (i < maxright)
            hw[i] = min(mid + hw[mid] - i, hw[2 * mid - i]);
        else
            hw[i] = 1;
        
        // 扩展回文半径
        while (t1[i - hw[i]] == t2[i + hw[i]])
            hw[i]++;
        
        // 更新最右边界
        if (i % 2 == 1 && hw[i] + i > maxright) {
            maxright = hw[i] + i;
            mid = i;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    cin >> s;
    s = ' ' + s;  // 调整为1-indexed
    t1 = ' ' + t1;
    t2 = ' ' + t2;
    t1.push_back('#');
    t2.push_back('#');
    
    // 构建t1和t2
    for (int i = 1; i <= n; i++) {
        t1.push_back(s[i]);      // t1: 原字符串
        t1.push_back('#');
        
        if (s[i] - '0' == 0)    // t2: 取反后的字符串
            t2.push_back('1');
        else
            t2.push_back('0');
        t2.push_back('#');
    }
    
    manacher();
    
    // 统计反对称子串数量
    for (int i = 1; i <= 2 * n + 1; i++) {
        if (t1[i] != '#') continue;  // 只统计中心在#的情况（偶数长度）
        ans += (hw[i] - 1) / 2;
    }
    
    cout << ans;
    return 0;
}

算法分析

时间复杂度

• Manacher算法：$O(n)$
• 总体复杂度：$O(n)$

空间复杂度

• 需要 $O(n)$ 的额外空间存储扩展字符串和回文半径数组

总结

解题关键：

1. 将反对称条件转化为两个字符串的匹配问题
2. 利用Manacher算法高效计算所有可能的反对称中心
3. 只考虑偶数长度的子串（中心在#）

技巧亮点：

• 构建原串和取反串进行匹配
• 利用Manacher算法的线性性质
• 通过插入特殊字符统一处理奇偶长度

这种将复杂条件转化为字符串匹配问题的方法，在解决对称性相关问题时非常有效。