P5685 [JSOI2013] 快乐的 JYY

Lu_xZ · 2024-07-28 01:46:29 · 题解

求数对 (l, r, x, y) 个数，满足：

一个回文串 s 对答案的贡献为 s 在 A 中出现的次数乘上 B 中出现的次数。

问题转化为求每种回文串的出现次数。

结论：一个串的本质不同回文串只有 O(n) 个。

所以可以枚举回文中心，先求出 2n 个极长回文串，如果当前串没有出现过，往中间缩减。

求出所有本质不同串后如何统计答案？

一个极长回文 s 会对 s, s[2, n - 1], s[3, n - 2] 产生 1 的贡献。

那么可以 s[2, n - 1] 连向 s，所有本质不同串形成森林，直接树上差分统计答案。

具体来说，x 会贡献 x 到根的一条链，在当前点加一即可。

（出题人应该把我所有能想到的单模卡了，所以要双模）

#include<bits/stdc++.h>
#define eb emplace_back
#define ep emplace
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
constexpr int B = 131, P = 998244353;
constexpr int B1 = 233, P1 = 1e9 + 7;

struct Node {
    int l, r;
    Node(int l = 0, int r = 0)
    : l(l), r(r) {}
};
ll p[50005], p1[50005];

auto F() {
    string s; int n;
    cin >> s, n = s.length();
    s = '#' + s;
    vector<ll> h(n + 2), g(n + 2), d(n + 2), e(n + 2);
    for(int i = 1; i <= n; ++ i) {
        h[i] = (h[i - 1] * B + s[i]) % P;
        d[i] = (d[i - 1] * B1 + s[i]) % P1;
    }
    for(int i = n; i >= 1; -- i) {
        g[i] = (g[i + 1] * B + s[i]) % P;
        e[i] = (e[i + 1] * B1 + s[i]) % P1;
    }
    auto get = [&](int l, int r, int o = 1) {
        ll x = (o ? h[r] : g[l]) - (o ? h[l - 1] : g[r + 1]) * p[r - l + 1];
        x = (x % P + P) % P;
        ll y = (o ? d[r] : e[l]) - (o ? d[l - 1] : e[r + 1]) * p1[r - l + 1];
        y = (y % P1 + P1) % P1;
        return make_pair(x, y); 
    };
    vector<Node> a;
    for(int i = 1; i <= n; ++ i) {
        int l = 1, r = min(i, n - i + 1);
        while(l < r) {
            int m = l + r + 1 >> 1;
            if(get(i, i + m - 1) == get(i - m + 1, i, 0)) {
                l = m;
            }
            else r = m - 1;
        }
        a.eb(i - l + 1, i + l - 1);
        if(i == n || s[i] != s[i + 1]) continue;
        l = 1, r = min(i, n - i);
        while(l < r) {
            int m = l + r + 1 >> 1;
            if(get(i + 1, i + m) == get(i - m + 1, i, 0)) {
                l = m;
            }
            else r = m - 1;
        }
        a.eb(i - l + 1, i + l);
    }
    vector G(10 * n, vector<int>{});
    vector<int> v(10 * n);
    map<pll, int> id; int tot = 0;

    for(auto [l, r] : a) {
        auto h = get(l, r);
        if(id.count(h)) continue;
        int x = id[h] = ++ tot;
        while(r - l > 1) {
            h = get(++ l, -- r);
            if(!id.count(h)) {
                G[id[h] = ++ tot].eb(x);
                v[x] = 1;
                x = tot;
            }
            else {
                G[id[h]].eb(x), v[x] = 1;
                break;
            }
        }
    }
    vector<ll> f(tot + 1);
    for(auto [l, r] : a) {
        ++ f[id[get(l, r)]];
    }
    auto dfs = [&](auto self, int x) -> void {
        for(int y : G[x]) {
            self(self, y);
            f[x] += f[y];
        }
    };
    for(int i = 1; i <= tot; ++ i) {
        if(!v[i]) dfs(dfs, i);
    }
    map<pll, ll> mp;
    for(auto [h, x] : id) mp[h] = f[x];
    return mp;
}
ll ans;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    p[0] = p1[0] = 1;
    for(int i = 1; i <= 50000; ++ i) {
        p[i] = p[i - 1] * B % P;
        p1[i] = p1[i - 1] * B1 % P1;
    }
    auto m1 = F(), m2 = F();
    for(auto [h, c] : m1) ans += c * m2[h];
    cout << ans;
    return 0;
}