形式化题目

给定长度为 $n$ 的 01 串 $s$。对字符串 $t$ 记 $\bar t$ 为逐位取反、$t^{R}$ 为整体反转；若 $(\bar t)^{R} = t$，称 $t$ 为反对称串。求 $s$ 的子串中反对称子串的个数（相同内容出现在不同位置各算一个）。

样例：$n = 8$，s = $ `11001011`，答案为 $7，即 01（出现两次）、10（出现两次）、0101、1100、001011。

正解

思路

1. 等价刻画：只可能是偶数长，按缝隙配对

把 $(\bar t)^{R} = t$ 按下标展开：反转把第 $i$ 位送到倒数第 $i$ 位，取反要求两边互补，即

下标 $i$ 与 $|t|-1-i$ 成对出现、没有不动点，所以 $|t|$ 一定是偶数——奇数长子串（含单字符）直接排除。于是子串 $s[l..r]$ 反对称当且仅当对每个偏移 $j$ 都有 $s_{l+j} \ne s_{r-j}$，即两个半串互为取反。

相邻两位之间的空隙称为缝隙（长度 $n$ 的串有 $n-1$ 个缝隙，缝隙 $g$ 夹在 $s_g$ 与 $s_{g+1}$ 之间，$0 \leqslant g \leqslant n-2$）。每个偶数长子串恰好关于唯一缝隙左右对称，因此按缝隙分组统计。定义缝隙 $g$ 的半径为

也就是从缝隙向两侧配出的连续"不等"对数。半径 $1, 2, \dots, f[g]$ 各对应一个反对称子串（长度 $2, 4, \dots, 2f[g]$），故

样例的 $f$ 如下表：

读表要点：每行以该缝隙为中心向两侧成对展开，$f[g]$ 就是这行能给出的子串个数。例如缝隙 4 的两侧是 …0 1…，向外三对依次是 $(s_4,s_5)$、$(s_3,s_6)$、$(s_2,s_7)$，字符两两不等，得到 10、0101、001011。各行相加 $2+1+3+1 = 7$，正是样例答案（01、10 各出现两次）。

2. 朴素做法与瓶颈

对每个缝隙直接向两侧一对一对比较，直到越界或遇到相等。全 0101… 串里每个缝隙都能扩满 $\Theta(n)$，总复杂度 $\Theta(n^2)$，$n = 500\,000$ 必然超时。瓶颈在于相邻缝隙的扩展高度重复：缝隙 $g$ 与 $g+1$ 比的字符对大面积重叠，"这一对不相等"的结论被反复重算。

3. Manacher 式优化：镜像继承 + 右端截断

回文 Manacher 消除重复的办法是：维护已知扩得最靠右的回文区间，区间内还没算的中心直接从它的镜像中心继承半径，只有超出右端的部分才真正比较。把判据"对应位置相等"换成"不等"，推理完全平行。

设已知最靠右的反对称区间为 $[l, r]$（由缝隙 $c$ 扩出，$l = c - f[c] + 1$，$r = c + f[c]$），当前要算的缝隙 $i$ 满足 $i < r$。它的镜像缝隙

必落在 $[l, i)$ 且已经算出，于是

两条理由缺一不可：

• 镜像继承：区间 $[l,r]$ 关于缝隙 $c$ 反对称，缝隙 $i'$ 的第 $j$ 对字符正是缝隙 $i$ 第 $j$ 对字符在区间内的镜像位置；而"取反不改变不等关系"（$a \ne b \iff \bar a \ne \bar b$），所以镜像缝隙配得出的每一对，缝隙 $i$ 也配得出。
• 右端截断：镜像关系给出恒等式 $r - i = i' - l + 1$，用 $r-i$ 截断恰好保证被继承的每一对字符都还落在 $[l, r]$ 内，结论才有效；右端之外没有现成结论，必须真正比较。

继承之后再用 while 继续向外扩展。均摊分析：继承来的比较一次都不执行；每个缝隙的 while 至多"失败一次"就终止；所有成功的比较其右端位置都在当前 $r$ 之外，且扩完该缝隙后新右端至少比旧 $r$ 多出的量不小于成功比较次数，而 $r$ 单调递增、至多到 $n-1$。故总比较次数 $O(n)$。

样例中缝隙 5 正好体现继承：处理它时区间已由缝隙 4 扩到 $[2,7]$（001011），镜像缝隙 $i' = 2+7-1-5 = 3$，$f[3] = 1$，于是 $f[5] \geqslant \min(1,\ 7-5) = 1$——$s_5 \ne s_6$ 这一对免于比较，只需补比区间外的一对 $s_4, s_7$（相等）即得 $f[5] = 1$。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 12:40
# update_at: 2026-09-30 12:40

import sys


def anti_manacher(s: bytes) -> int:
    """统计 01 串中反对称子串的个数。

    对每个缝隙 g 求 f[g]：以 g 为中心、左右两侧字符必须"不等"的最大配对数
    （半径）。半径从 1 到 f[g] 的每一段都是反对称子串，所以答案为 sum(f)。
    把 Manacher 的"相等"比较换成"不等"：若区间 [l, r] 关于缝隙 cg 反对称，
    则右半边的缝隙 i 能从镜像缝隙 l+r-1-i 继承半径 min(f[mirror], r-i)，
    剩下的比较都发生在旧区间右端之外，总比较次数均摊 O(len)。
    """
    n = len(s)
    f = [0] * (n - 1)  # f[g]：缝隙 g 两侧最多配出多少对"不等"
    ans = 0
    l, r = 0, -1       # 已知最靠右的反对称区间 [l, r]，初始为空
    for i in range(n - 1):
        if i < r:
            k = min(f[l + r - 1 - i], r - i)  # 镜像缝隙必在左半边且已计算
        else:
            k = 0
        while i - k >= 0 and i + 1 + k < n and s[i - k] != s[i + 1 + k]:
            k += 1
        f[i] = k
        ans += k
        if k and i + k > r:  # 摸到更靠右的反对称区间才更新
            l, r = i - k + 1, i + k
    return ans


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))  # 题面的 N，与 len(s) 相同，仅作输入格式注解
    s = next(data)
    print(anti_manacher(s))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49// main.cpp：把回文 Manacher 的"相等"判据换成"不等"，统计反对称子串个数。
// 反对称串长度必为偶数，按缝隙统计：缝隙 g 的半径 f[g] = 两侧最多配出的
// "不等"对数，每个半径 1..f[g] 对应一个反对称子串，答案为 sum(f[g])。
// 用最靠右反对称区间做"镜像继承 + 右端截断"，总复杂度 O(n)。

/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-13 15:42
 * update_at: 2026-10-13 15:42
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 500005;

int n;
char s[MAXN];   // s[i]：第 i 位字符（0..n-1），读入后存成 0/1 的 int 差值
int f[MAXN];    // f[g]：缝隙 g（夹在 s[g] 与 s[g+1] 之间）两侧最多配出的"不等"对数

int main() {
    scanf("%d %s", &n, s);
    for (int i = 0; i < n; ++i) s[i] -= '0'; // 转成数值，便于比较

    ll ans = 0;
    int l = 0, r = -1; // 已知最靠右的反对称区间 [l, r]，初始为空
    for (int i = 0; i < n - 1; ++i) {
        int k = 0;
        if (i < r) {
            // 镜像缝隙 l+r-1-i 必在左半边且已算出：
            // 取反不改变不等关系，故可继承 min(f[mirror], r-i)
            k = f[l + r - 1 - i];
            if (k > r - i) k = r - i; // 右端截断：继承的对必须落在 [l, r] 内
        }
        // 只有区间右端之外或首次失败的比较才真正执行，均摊 O(n)
        while (i - k >= 0 && i + 1 + k < n && s[i - k] != s[i + 1 + k]) k += 1;
        f[i] = k;
        ans += k; // 半径 1..k 各对应一个反对称子串
        if (k > 0 && i + k > r) { // 摸到更靠右的反对称区间才更新
            l = i - k + 1;
            r = i + k;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

与推导的对应关系：

• f[i] 就是缝隙 $i$ 的半径，ans += k 完成 $\sum f[g]$；
• l, r 是最靠右的反对称区间，k = min(f[l + r - 1 - i], r - i) 即"镜像继承 + 右端截断"；
• while ... s[i - k] != s[i + 1 + k] 把回文判据换成"不等"，只执行右端之外或首次失败的比较；
• if k and i + k > r: l, r = i - k + 1, i + k 只在扩出更靠右的区间时更新；
• 读入用 sys.stdin.buffer.read().split() 一次完成，$N$ 只作输入格式注解。

复杂度

• 时间复杂度：$O(n)$。区间内的比较全部由镜像继承免费获得，越界成功比较把右端 $r$ 单调推进（总量 $O(n)$），每个缝隙至多一次失败比较。
• 空间复杂度：$O(n)$，主要是一维数组 f，满足 128MB 限制。
• 本地以仓库脚本对 62 组真实测试数据全部跑通，输出与答案完全一致（本地按惯例放宽限时、不设内存硬限）。

总结

反对称的定义要先"翻译"成可操作条件：长度必为偶数，且关于某个缝隙左右镜像的位置字符互不相等。计数随即变成"每个缝隙能向外配多少对"，单缝隙暴力扩展是 $\Theta(n^2)$。把回文 Manacher 的"相等"判据整体换成"不等"——取反恰好保持不等关系——配合最靠右反对称区间的镜像继承与 $r-i$ 右端截断，就能把重复比较全部消掉，$O(n)$ 求出每个缝隙的半径并求和。