Problem A: 余命六十日

🔑 算法模块

KMP

💡 思路分析

注意到题目给出的限制十分恶心（至少有一对的处理很麻烦，需要容斥），考虑计算补集，然后用全集减去补集。

全集很容易计算，每个位置只有选和不选两种，数量为 \(2^{|S|}\)。

考虑计算补集，也就是不存在两个下标 \(x,y\) 满足前缀 \(x\) 是前缀 \(y\) 的后缀的下标集合数量。

注意如果要满足前缀 \(x\) 是前缀 \(y\) 的后缀，首先需要满足 \(x \lt y\)，也就是前缀 \(x\) 是前缀 \(y\) 的前缀。

因此，如果满足这一条件，\(x\) 一定是 \(y\) 的相等真前后缀，也就是 Border。

问题转化为：求有多少个下标集合满足其中不存在两个下标 \(x,y\) 满足 \(x\) 是 \(y\) 的 Border。

注意到 Border 性质：一个字符串的最长 Border 的最长 Border 是其次长 Border（证明可以使用反证法，这也是 KMP 算法的重要性质），字符串的所有前缀按最长 Border 关系可以构成一棵 \(|S|+1\) 个结点的有根树。

方法为：通过 KMP 等算法求出每个前缀 \(i\) 的最长 Border 记为 \(nxt_i\)，每个结点 \(u\) 将 \(nxt_u\) 作为父亲，即可得到一棵以 \(0\) 号结点为根的有根树，结点 \(u\) 的所有祖先都是它的 Border。该树也被称为 KMP Fail 树。

那么，问题转化为：在一棵有根树上选出一个点集使得任意两点都没有祖先后代关系，求方案数量。

考虑动态规划：设 \(dp_u\) 为结点 \(u\) 的子树中，强制不选结点 \(u\) 的答案。

初始状态为 \(dp_u=1\)，转移为 \(dp_u=\prod_{v\in\operatorname{child}_u}(dp_v+1)\)，答案即为 \(dp_0\)。

实际上，我们并不需要显式地建树：倒序地从 \(|S|\) 到 \(1\) 枚举 \(i\)，按 \(dp_{nxt_i}\leftarrow dp_{nxt_i}\times (dp_i+1)\) 转移即可，原因留给读者自行考虑。

答案为 \(2^{|S|}-dp_0\)，注意取模。

时间复杂度 \(\Theta(t|S|)\)。

std:

#include<bits/stdc++.h>

using i64 = long long;
const int mod = 998244353;

std::vector<int> Get(std::string s) {
    int n = s.length();
    std::vector<int> a(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        int j = a[i - 1];
        while (j && s[j] != s[i - 1]) {
            j = a[j];
        }
        if (s[i - 1] == s[j]) {
            j++;
        }
        a[i] = j;
    }
    return a;
}

void solve() {
    std::string s;
    std::cin >> s;
    int n = s.size();
    int ans = 1;
    std::vector a = Get(s);
    std::vector<i64> dp(n + 1, 1);
    for (int i = n; i > 0; i--) {
        ans = ans * 2 % mod;
        dp[a[i]] = (dp[a[i]] * (dp[i] + 1) % mod) % mod;
    }
    ans = (ans - dp[0] + mod) % mod;
    std::cout << ans << "\n";
}

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

    int _ = 1;
    std::cin >> _;
    while (_--) {
        solve();
    }

    return 0;
}