「CF2174C2」Beautiful Patterns (Hard Version)

发表于 分类于 本文字数： 979 阅读时长 ≈ 4 分钟

Description

Link：CF2174C2

已知一个字符串 SS 的长度为 nn，字符集大小为 mm。现在均匀随机地生成该字符串 SS。

记随机变量 XX 表示该字符串 SS 中回文子串的数量，求 E(X2)E(X^2)。答案对给定质数 pp 取模。

数据范围：1≤n≤2×1051 \leq n \leq 2 \times 10^5，1≤m≤1071 \leq m \leq 10^7，m<p<109m < p < 10^9。

时空限制：22s / 512512MiB。

Solution

平方的期望是一个经典 Trick。记 xl,rx_{l, r} 表示区间 [l,r][l, r] 是否回文，则

E(X2)=E((∑1≤l≤r≤nxl,r)2)=E(∑l1≤r1,l2≤r2xl1,r1⋅xl2,r2)=∑l1≤r1,l2≤r2E(xl1,r1⋅xl2,r2)\begin{aligned} E(X^2) & = E\left(\left( \sum_{1 \leq l \leq r \leq n} x_{l, r} \right)^2 \right) \\ & = E\left( \sum_{l_1 \leq r_1, l_2 \leq r_2} x_{l_1, r_1}\cdot x_{l_2, r_2} \right) \\ & = \sum_{l_1 \leq r_1, l_2 \leq r_2} E\left( x_{l_1, r_1}\cdot x_{l_2, r_2} \right) \end{aligned}

相当于是计算，任意取出两个区间，均为回文串的概率之和。

若两个区间共用一个回文中心，则概率为较长串为回文串的概率。

若两个区间不共用一个回文中心，有一个很深刻的事实：两个区间是否回文是相互独立的。

简单证明

对于一个回文区间 [l,r][l, r]，相当于是将二元组 (l,r),(l+1,r−1),⋯(l, r), (l + 1, r - 1), \cdots 位置上的字符进行合并。显然每次有效的合并（两点在之前不连通），都会导致自由元个数减少一个。

我们可以证明：每次合并都有效，即这样连边一定不会出现环。所以自由元的损失个数即为实际边数。

对于一个回文中心来说，产生的边的端点之和必定为 l+rl + r。记两个回文中心的端点之和分别为 C1,C2C_1, C_2。则 xx 应用变换 1 得到 C1−xC_1 - x，应用变换 2 得到 C2−xC_2 - x。

假设连边会出现环，则一定存在一个 xx 经过一条简单路径再次回到 xx。由于同一种变换不能连续使用（不然就形成了重边），不妨设变换 1, 2 交替使用：

  • 偶数次变换：得到 x+k(C2−C1)x + k(C_2 - C_1)，由于 C1≠C2C_1 \neq C_2，因此必定不等于 xx。
  • 奇数次变换：假设回到了 xx，则必然是从 C1−xC_1 - x 回到 xx 的。但这是一条重边，而不是一个环。

Q.E.D

然后按照是否共用一个回文中心，分两类计算贡献即可。

时间复杂度 O(n)\mathcal{O}(n)。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

#define debug(a) std::cout << #a << "=" << (a) << ' '

template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

const int N = 200100;

int n, m, mod;

inline void add(int &x, const int &y) {
    x += y;
    if (x >= mod) {
        x -= mod;
    }
}
inline void dec(int &x, const int &y) {
    x -= y;
    if (x < 0) {
        x += mod;
    }
}
inline int norm(int x) {
    x %= mod;
    return x < 0 ? x + mod : x;
}

constexpr int qpow(int a, int b, int p) {
    int ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
    }
    return ans;
}

int im;

int power[N], pre[N];
int s0[N], s1[N];

void work() {
    std::cin >> n >> m >> mod;

    im = qpow(m, mod - 2, mod);

    power[0] = 1;
    for (int i = 1; i <= n; i ++) {
        power[i] = 1ll * power[i - 1] * im % mod;
    }

    pre[0] = 1;
    for (int i = 1; i <= n; i ++) {
        add(pre[i] = pre[i - 1], power[i]);
    }

    s0[0] = 0;
    for (int i = 1; i <= n; i ++) {
        add(s0[i] = s0[i - 1], 1ll * power[i] * i % mod);
    }

    s1[0] = 0;
    for (int i = 1; i <= n; i ++) {
        add(s1[i] = s1[i - 1], 1ll * power[i] * (i - 1) % mod);
    }

    int ans1 = 0, ans2 = 0, sum = 0;
    for (int i = 1; i <= n; i ++) { // 0~u
        int u = std::min(i - 1, n - i);
        int cur = pre[u];

        add(ans1, cur);
        add(ans2, s0[u]);

        add(ans2, 1ll * cur * sum % mod);
        add(sum, cur);
    }
    for (int i = 1; i < n; i ++) { // 1~u
        int u = std::min(i, n - i);
        int cur = norm(pre[u] - 1);

        add(ans1, cur);
        add(ans2, s1[u]);

        add(ans2, 1ll * cur * sum % mod);
        add(sum, cur);
    }

    int ans = (ans1 + 2ll * ans2) % mod;
    std::cout << ans << '\n';
}

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

    int T;
    std::cin >> T;
    
    while (T --) {
        work();
    }

    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/