E. Palisection - 题解

比赛与标签

比赛: Codeforces Beta Round 17 标签: strings, *2900 难度: *2900

题目大意喵~

主人你好呀~ 这道题是关于回文串的计数问题哦！(ฅ'ω'ฅ)

题目是这样哒：给定一个长度为 n 的字符串，我们需要找出其中所有的回文子串。然后，我们要计算有多少对不同的回文子串，它们在原字符串中的位置是相交的。

"相交" 是指两个回文子串占据了至少一个共同的位置。比如说，在字符串 babb 中：

• bab (位置 1..3) 和 bb (位置 3..4) 是相交的，因为它们都占据了位置 3。
• b (位置 1..1) 和 a (位置 2..2) 是不相交的。

我们要做的就是算出所有这些相交的回文子串对的总数，最后结果要对 51123987 取模哦~

解题思路喵~

直接去数相交的对数，感觉会很复杂，头都大了喵~ (´-ω-`) 不如我们换个思路，采取正难则反的策略！

我们可以先算出所有回文子串的总对数，然后减去所有不相交的回文子串对数，剩下的不就是相交的对数了嘛？是不是很机智呀~

总相交对数 = 总回文子串对数 - 不相交回文子串对数

好，那我们的任务就分解成两步啦：

1. 计算总共有多少个回文子串。
2. 计算有多少对回文子串是不相交的。

第一步：找到所有回文子串

要快速找到一个字符串里所有的回文子串，最经典的算法就是 Manacher (马拉车) 算法 啦！它可以在 O(n) 的时间内，计算出以每个字符为中心（奇数长度）或每两个字符之间为中心（偶数长度）的最长回文半径。

• 对于奇数长度的回文串，以 s[i] 为中心，最长回文半径记为 d1[i]。这表示有 d1[i] 个以 s[i] 为中心的回文串（长度分别为 1, 3, ..., 2*d1[i]-1）。
• 对于偶数长度的回文串，以 s[i-1] 和 s[i] 的间隙为中心，最长回文半径记为 d2[i]。这表示有 d2[i] 个以这个间隙为中心的回文串（长度分别为 2, 4, ..., 2*d2[i]）。

所以，回文子串的总数 total_pal 就是所有 d1[i] 和 d2[i] 的总和。 total_pal = ∑d1[i] + ∑d2[i]

有了总数，总的配对数就是从 total_pal 个回文串中任选两个，即 C(total_pal, 2) = total_pal * (total_pal - 1) / 2。因为要取模，除以 2 就要变成乘以 2 的模逆元哦！

第二步：计算不相交的对数

两个回文子串 P1（区间 [l1, r1]）和 P2（区间 [l2, r2]）不相交，当且仅当一个完全在另一个的前面。不失一般性，我们假设 l1 < l2，那么不相交的条件就是 r1 < l2。

要统计所有这样的对，我们可以从左到右遍历字符串的每一个位置 i。我们想知道，对于所有以 i 为起点的回文串，有多少个回文串在它之前就已经结束了？

为了实现这个想法，我们需要两个信息：

1. start_count[i]：以位置 i 为起点的回文子串数量。
2. end_count[i]：以位置 i 为终点的回文子串数量。

如果我们能高效地算出这两个数组，就可以这样计算不相交对数了： 我们从 i = 0 到 n-1 遍历，维护一个变量 ended_so_far，表示到当前位置 i-1 为止，已经结束的回文串总数。 ended_so_far = ∑_{j=0}^{i-1} end_count[j]

那么，在位置 i，不相交的对数就增加了 start_count[i] * ended_so_far。 所以，总的不相交对数就是： non_crossing = ∑_{i=0}^{n-1} (start_count[i] * (∑_{j=0}^{i-1} end_count[j]))

第三步：如何高效计算 start_count 和 end_count？

这一步是关键喵！我们还是利用 Manacher 算法的结果。

• 一个以 i 为中心的奇数长度回文串，半径为 k (1 ≤ k ≤ d1[i])，它的起始位置是 i-k+1，结束位置是 i+k-1。
• 一个以 i-1 和 i 之间为中心的偶数长度回文串，半径为 k (1 ≤ k ≤ d2[i])，它的起始位置是 i-k，结束位置是 i+k-1。

这意味着，对于一个中心 i，它贡献了多个回文串，这些回文串的起点和终点都形成了一个连续的区间！

• 对于 d1[i]：
  • 起点在区间 [i - d1[i] + 1, i] 内。
  • 终点在区间 [i, i + d1[i] - 1] 内。
• 对于 d2[i]：
  • 起点在区间 [i - d2[i], i - 1] 内。
  • 终点在区间 [i, i + d2[i] - 1] 内。

对一个区间内的所有数都加 1，这不就是经典的差分数组应用场景嘛！我们可以创建两个差分数组 A 和 B，分别对应 start_count 和 end_count。

• 要给 count[l...r] 都加 1，我们只需 diff[l]++ 和 diff[r+1]--。
• 最后对差分数组求一遍前缀和，就能得到真实的 count 数组啦！

整个过程都是 O(n) 的，完美解决！

总结一下流程：

1. 用 Manacher 算法求出 d1 和 d2 数组。
2. 累加 d1 和 d2 得到回文串总数 total_pal。
3. 计算总对数 total_pairs = (total_pal * (total_pal - 1) / 2) % mod。
4. 建立差分数组 A 和 B。遍历所有中心点，根据 d1 和 d2 的值更新差分数组。
5. 对 A 和 B 求前缀和，得到 start_count 和 end_count 数组。
6. 遍历一遍，计算不相交对数 non_crossing。
7. 最终答案就是 (total_pairs - non_crossing + mod) % mod。

这样，我们就在线性的时间复杂度内解决了问题，太棒了喵~！

代码实现喵~

#include <iostream>
#include <vector>
using namespace std;

// 题目给定的模数
const int mod = 51123987;
// 2 在模下的逆元，用来计算组合数 C(n, 2)
const long long inv2 = (mod + 1) / 2;

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    // d1[i]: 以 i 为中心的奇数长度回文串的半径 (长度=2*d1[i]-1)
    // d2[i]: 以 i-1 和 i 之间为中心的偶数长度回文串的半径 (长度=2*d2[i])
    vector<int> d1(n, 0), d2(n, 0);

    // Manacher 算法计算 d1 (奇数长度)
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) {
            k++;
        }
        d1[i] = k;
        if (i + k - 1 > r) {
            l = i - k + 1;
            r = i + k - 1;
        }
    }

    // Manacher 算法计算 d2 (偶数长度)
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) {
            k++;
        }
        d2[i] = k;
        if (i + k - 1 > r) {
            l = i - k;
            r = i + k - 1;
        }
    }

    // 计算回文子串总数
    long long total_pal = 0;
    for (int i = 0; i < n; i++) {
        total_pal += d1[i] + d2[i];
    }

    // A 是 start_count 的差分数组, B 是 end_count 的差分数组
    vector<long long> A(n + 2, 0), B(n + 2, 0);

    // 根据 d1 和 d2 的结果，填充差分数组
    // 每一个中心点都贡献了一系列回文串，它们的起点和终点构成区间
    for (int i = 0; i < n; i++) {
        if (d1[i] > 0) {
            // 奇数回文串，中心 i，半径从 1 到 d1[i]
            // 起点区间: [i - d1[i] + 1, i]
            int l_start = i - d1[i] + 1;
            int r_start = i;
            A[l_start]++;
            A[r_start + 1]--;
            // 终点区间: [i, i + d1[i] - 1]
            int l_end = i;
            int r_end = i + d1[i] - 1;
            B[l_end]++;
            B[r_end + 1]--;
        }
    }
    for (int i = 0; i < n; i++) {
        if (d2[i] > 0) {
            // 偶数回文串，中心 i-1 和 i 之间，半径从 1 到 d2[i]
            // 起点区间: [i - d2[i], i - 1]
            int l_start = i - d2[i];
            int r_start = i - 1;
            if (l_start <= r_start) {
                A[l_start]++;
                A[r_start + 1]--;
            }
            // 终点区间: [i, i + d2[i] - 1]
            int l_end = i;
            int r_end = i + d2[i] - 1;
            B[l_end]++;
            B[r_end + 1]--;
        }
    }

    // 通过前缀和计算真实的 start_count 和 end_count
    vector<long long> start_count(n, 0), end_count(n, 0);
    long long curA = 0, curB = 0;
    for (int i = 0; i < n; i++) {
        curA = (curA + A[i]) % mod;
        start_count[i] = curA;
        curB = (curB + B[i]) % mod;
        end_count[i] = curB;
    }

    // 计算不相交的回文子串对数
    long long non_crossing = 0;
    long long prev_end_sum = 0; // 记录到 i-1 为止结束的回文串总数
    for (int i = 0; i < n; i++) {
        // 对于所有以 i 开头的回文串，它们与在 i 之前结束的回文串都不相交
        non_crossing = (non_crossing + start_count[i] * prev_end_sum) % mod;
        // 更新已结束的回文串总数
        prev_end_sum = (prev_end_sum + end_count[i]) % mod;
    }

    // 计算总的回文子串对数
    total_pal %= mod;
    long long total_pairs = (total_pal * (total_pal - 1)) % mod;
    total_pairs = total_pairs * inv2 % mod;

    // 总对数减去不相交对数，得到相交对数
    long long ans = (total_pairs - non_crossing + mod) % mod;
    cout << ans << endl;

    return 0;
}

复杂度分析

• 时间复杂度: O(n) 的说。

  • Manacher 算法的两个循环都是 O(n) 的。
  • 填充差分数组是 O(n) 的，因为每个中心点只产生两个区间的更新。
  • 从差分数组计算 start_count 和 end_count 是 O(n) 的。
  • 最后计算不相交对数也是 O(n) 的。
  • 所以总的时间复杂度就是 O(n) 啦，非常高效！

• 空间复杂度: O(n) 的说。

  • 我们需要 d1, d2, A, B, start_count, end_count 这些数组来存储中间结果，它们的大小都和字符串长度 n 成正比。所以空间复杂度是 O(n)。

知识点与总结

这道题真是一道非常棒的字符串综合题呢，喵~ 它考察了我们好几个重要的知识点：

1. 逆向思维 (正难则反): 当直接求解困难时，尝试计算它的补集（总数 - 不满足条件的数量）是一个非常重要的解题思想。
2. Manacher 算法: 解决回文串问题的神器！是线性时间内找出所有回文子串信息的核心。
3. 差分与前缀和: 这是一对好朋友！差分数组可以把多次区间修改操作的复杂度降下来，最后通过一次前缀和还原出原数组。在这里，它被巧妙地用来统计所有回文串的起点和终点分布。
4. 模块化解题: 把一个大问题分解成几个小步骤（求总数 -> 求不相交数 -> 最终相减），让思路更清晰，代码也更容易实现。
5. 模运算: 在计数问题中，别忘了处理取模，特别是除法要用乘法逆元来代替哦。

希望这篇题解能帮助到你，一起享受解题的乐趣吧！加油喵~ (๑•̀ㅂ•́)و✧