CF1205E

题意

定义 f(s)f(s) 表示字符串 ss 的 border 的个数。

求字符集大小为 kk，长度为 nn 的字符串 f(s)2f(s)^2 的期望。

题解

g(s,i)g(s,i) 表示 s[1:i]s[1:i] 是否为 ss 的 border。重要性质： border   ⟺  \iff 周期。

f(s)2=∑i=1n∑j=1n[g(s,i)∧g(s,j)]f(s)^2=\sum_{i=1}^{n}\sum_{j=1}^n [g(s,i)\wedge g(s,j)]

E=1kn∑s∑i=1n−1∑j=1n−1[g(s,i)∧g(s,j)]=1kn∑s∑i=1n−1[g(s,i)]∑j=1n−1[g(s,j)]=1kn∑i=1n−1∑j=1n−1∑s[ s 有 i 周期，j 周期 ]=1kn∑i=1n−1∑j=1n−1∑s[ gcd⁡(i,j) 是 s 的周期 ]\begin{aligned} \mathbb{E}=&\frac{1}{k^n} \sum_{s} \sum_{i=1}^{n-1}\sum_{j=1}^{n-1} [g(s,i)\wedge g(s,j)]\\ =&\frac{1}{k^n} \sum_{s} \sum_{i=1}^{n-1}[g(s,i)]\sum_{j=1}^{n-1} [g(s,j)]\\ =&\frac{1}{k^n} \sum_{i=1}^{n-1} \sum_{j=1}^{n-1} \sum_{s} [ \text{ $s$ 有 $i$ 周期，$j$ 周期 }]\\ =&\frac{1}{k^n} \sum_{i=1}^{n-1} \sum_{j=1}^{n-1} \sum_{s} [ \text{ $\gcd(i,j)$ 是 $s$ 的周期 }]\\ \end{aligned}

考虑 ∑s[ s 有 i 周期，j 周期 ]\sum_{s} [\text{ s 有 i 周期，j 周期 }]，ss 的某些位置是相同的，我们要求的是「自由的位置」有多少个。考虑一张图，图上两点联通对应 ss 中两个位置相同，那么所有  mod i\bmod i 相同的数连边，所以  mod j\bmod j 相同的数连边。要算的是联通块的个数。证明看这里吧，我们最终得到联通块的个数为 max⁡(gcd⁡(i,j),i+j−n)\max(\gcd(i,j),i+j-n) 。

∑i=1n−1∑j=1n−1kmax⁡(gcd⁡(i,j),i+j−n)\sum_{i=1}^{n-1}\sum_{j=1}^{n-1} k^{\max(\gcd(i,j),i+j-n)}

max⁡(gcd⁡(i,j),i+j−n)\max(\gcd(i,j),i+j-n) 考虑先钦定 max⁡\max 为 i+j−ni+j-n：

∑i=1n−1∑j=1n−1ki+j−n=1kn∑i=1n−1∑j=1n−1ki+j\sum_{i=1}^{n-1}\sum_{j=1}^{n-1} k^{i+j-n}=\frac{1}{k^n} \sum_{i=1}^{n-1}\sum_{j=1}^{n-1} k^{i+j}

这个好算。再考虑 gcd⁡(i,j)>i+j−n\gcd(i,j)>i+j-n，令 m=n−1m=n-1。

∑d=1m∑i=1m∑i=1m[gcd⁡(i,j)=d][d>i+j−n](kd−ki+j−n)=∑d=1m∑i=1⌊m/d⌋∑i=1⌊m/d⌋[gcd⁡(i,j)=1][d>d(i+j)−n](kd−kd(i+j)−n)=∑d=1m∑i=1⌊m/d⌋∑i=1⌊m/d⌋[gcd⁡(i,j)=1][(i+j)<1+⌊n/d⌋](kd−kd(i+j)−n)=∑d=1m∑s=2⌊n/d⌋∑i=1s−1[gcd⁡(i,s−i)=1](kd−kds−n)=∑d=1m∑s=2⌊n/d⌋∑i=1s−1[gcd⁡(i,s)=1](kd−kds−n)\begin{aligned} &\quad\sum_{d=1}^{m} \sum_{i=1}^{m} \sum_{i=1}^{m} [\gcd(i,j)=d] [d>i+j-n] (k^{d}-k^{i+j-n})\\ &=\sum_{d=1}^{m} \sum_{i=1}^{\left\lfloor m/d\right\rfloor} \sum_{i=1}^{\left\lfloor m/d\right\rfloor} [\gcd(i,j)=1] [d>d(i+j)-n] (k^{d}-k^{d(i+j)-n})\\ &=\sum_{d=1}^{m} \sum_{i=1}^{\left\lfloor m/d\right\rfloor} \sum_{i=1}^{\left\lfloor m/d\right\rfloor} [\gcd(i,j)=1] [(i+j)<1+\left\lfloor n/d\right\rfloor] (k^{d}-k^{d(i+j)-n})\\ &=\sum_{d=1}^{m} \sum_{s=2}^{\left\lfloor n/d\right\rfloor} \sum_{i=1}^{s-1} [\gcd(i,s-i)=1] (k^{d}-k^{ds-n})\\ &=\sum_{d=1}^{m} \sum_{s=2}^{\left\lfloor n/d\right\rfloor} \sum_{i=1}^{s-1} [\gcd(i,s)=1] (k^{d}-k^{ds-n})\\ \end{aligned}

显然右边括号拆开，左边的：

∑d=1m∑s=2⌊n/d⌋∑i=1s−1[gcd⁡(i,s)=1]kd=∑d=1m∑s=2⌊n/d⌋φ(s)kd=∑d=1mkd∑s=2⌊n/d⌋φ(s)\begin{aligned} &\quad \sum_{d=1}^{m} \sum_{s=2}^{\left\lfloor n/d\right\rfloor} \sum_{i=1}^{s-1} [\gcd(i,s)=1] k^{d}\\ &=\sum_{d=1}^{m} \sum_{s=2}^{\left\lfloor n/d\right\rfloor} \varphi(s) k^{d}\\ &=\sum_{d=1}^{m} k^{d}\sum_{s=2}^{\left\lfloor n/d\right\rfloor} \varphi(s) \\ \end{aligned}

预处理 φ\varphi 随便算，O(n)O(n) 的。右边：

∑d=1m∑s=2⌊n/d⌋∑i=1s−1[gcd⁡(i,s)=1]kds−n=1kn∑d=1m∑s=2⌊n/d⌋φ(s)kds\begin{aligned} &\quad \sum_{d=1}^{m} \sum_{s=2}^{\left\lfloor n/d\right\rfloor} \sum_{i=1}^{s-1} [\gcd(i,s)=1] k^{ds-n}\\ &=\frac{1}{k^n}\sum_{d=1}^{m} \sum_{s=2}^{\left\lfloor n/d\right\rfloor} \varphi(s) k^{ds}\\ \end{aligned}

调和级数，O(nlog⁡n)O(n\log n)，那么完事了。

CODE

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
#include <bits/stdc++.h>
template <typename Tp>
inline void read(Tp& x) {
    x = 0; bool fg = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') fg ^= 1; ch = getchar();}
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
    if (fg) x = -x;
}
template <typename Tp, typename... Args>
void read(Tp& t, Args& ...args) { read(t); read(args...); }
using namespace std;
typedef long long ll;
const int N = 100010;
const int mod = 1e9 + 7;
int n, k;
int p[N], phi[N], tot;
bool v[N];
void init(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) p[++tot] = i, phi[i] = i - 1;
        for (int j = 1; j <= tot && p[j] * i <= n; ++j) {
            v[i * p[j]] = 1;
            if (i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
            phi[i * p[j]] = phi[i] * (p[j] - 1);
        }
    }
    phi[1] = 1;
}
ll qpow(ll a, ll b = mod - 2) {
    if (b < 0) return qpow(qpow(a, -b));
    ll r = 1;
    for ( ; b; b >>= 1, a = a * a % mod) if (b & 1) r = r * a % mod;
    return r;
}
int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}
template <typename Tp>
void Add(Tp &x, Tp y) {
    x = (x + y) % mod;
}
template <typename Tp>
void Sub(Tp &x, Tp y) {
    x = ((x - y) % mod + mod) % mod;
}

template <typename Tp>
void Mul(Tp &x, Tp y) {
    x = x * y % mod;
}
void baoli() {
    ll ans = 0;
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            Add(ans, qpow(k, max(i + j - n, gcd(i, j))));
        }
    }
    Mul(ans, qpow(qpow(k, n)));
    cout << ans << endl;
}
int main() {
    cin >> n >> k; init(n);
    ll ans = 0, pw = k;
    for (int s = 2; s <= 2 * n - 2; ++s) {
        Mul(pw, (ll)k);
        int cnt = (s <= n) ? (s - 1) : (2 * n - 1 - s);
        Add(ans, pw * cnt % mod);
    }
    Mul(ans, qpow(qpow(k, n)));
    ll tp1 = 0, tp2 = 0;
    pw = 1;
    for (int d = 1; d < n; ++d) {
        Mul(pw, (ll)k);
        ll tmp = 0;
        for (int s = 2; d * s - d < n; ++s) Add(tmp, (ll)phi[s]);
        Add(tp1, pw * tmp % mod);
    }
    for (int d = 1; d < n; ++d) {
        ll tmp = 0, dt = qpow(k, d);
        pw = dt;
        for (int s = 2; d * s - d < n; ++s) {
            Mul(pw, dt);
            Add(tmp, pw * phi[s] % mod);
        }
        Add(tp2, tmp);
    }
    Mul(tp2, qpow(qpow(k, n)));
    ans = (ans + tp1 - tp2 + mod) % mod;
    Mul(ans, qpow(qpow(k, n)));
    cout << ans << endl;
    return 0;
}