题意

定义 $f(s)$ 表示字符串 $s$ 的 border 数量。给定 $n,k$，求长度为 $n$，字符集大小为 $k$ 的字符串 $s$ 的 $f(s)^2$ 的期望值。

$1 \le n \le 10^5,1 \le k \le 10^9$。

分析

弱化版：求 $f(s)$ 的期望值

我们发现，直接求 border 期望数量不好做，要用到一个经典的结论。

对于字符串 $s$ 的一个长度为 $i$ 的 border，这个字符串存在一个长度为 $|s| - i$ 的周期。

这个结论告诉我们一个 border 对应一个周期。考虑枚举 $i$，求有多少个字符串以 $i$ 为周期。考虑把所有 $x,x+i$ 连边，那么就是在同一个连通块内的位置要用相同字符。假设有 $cnt$ 个连通块，那么 $i$ 周期就有 $k^{cnt}$ 的贡献。这里的 $cnt$ 就是 $i$。所以答案就是 $\frac{\sum k^i}{k^n}$。

回到这题：求 $f(s)^2$ 的期望值

按照上面的思路，我们枚举 $i,j$，求有多少个字符串同时以 $i,j$ 为周期。把所有 $x,x+i$ 和 $x,x+j$ 连起来，设有 $cnt$ 个连通块，那么同样有 $k^{cnt}$ 的贡献。但是这里的 $cnt$ 怎么算呢？

经过打表之后，发现 $cnt = \max(\gcd(i,j),i+j-n)$。想看证明的可以直接去代码后面看，这里先假设我们知道了这个结论。

那么我们现在就是要求 $\sum_{i=1}^{n-1} \sum_{j=1}^{n-1} k^{\max(\gcd(i,j),i+j-n)}$。考虑枚举指数，求有多少个 $(i,j)$ 以这个为指数。

我们可以枚举 $s=i+j,g=\gcd(i,j)$，因为 $g|s$。枚举的时间复杂度就是 $O(n\log n)$ 的。我们现在要求的就是下面的式子。

$$\sum_{i=\max(s-n+1,1)}^{\min(s-1,n-1)}[\gcd(i,s-i)=g]$$
$$=\sum_{i=\max(1,\frac{s}{g}-\left \lfloor \frac{n-1}{g} \right \rfloor )}^{\min(\left \lfloor \frac{n-1}{g} \right \rfloor ,\frac{s}{g}-1)} [\gcd(i,s-i)=1]$$

设 $l = \max(1,\frac{s}{g}-\left \lfloor \frac{n-1}{g} \right \rfloor ),r=\min(\left \lfloor \frac{n-1}{g} \right \rfloor ,\frac{s}{g}-1)$，根据莫比乌斯反演，我们可以得到下式。

$$=\sum_{d|\frac{s}{g}} \mu(d) \sum_{i=l}^r [d|i]$$
$$=\sum_{d|\frac{s}{g}} \mu(d)(\left \lfloor \frac{r}{d} \right \rfloor - \left \lfloor \frac{l-1}{d} \right \rfloor )$$

于是我们可以枚举 $s,g,d$，时间复杂度就是 $O(n\log^2n)$ 的。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define N 200005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
const int P = 1e9 + 7;
int n, k, ans, pr[N], mu[N], flag[N], cnt, pwk[N];
vector <int> D[N];
il int ksm(int x, int r){
    int ans = 1;
    for (; r; x = 1ll * x * x % P, r >>= 1) if (r & 1) ans = 1ll * ans * x % P;
    return ans;
}
signed main(){
    n = rd(), k = rd();
    mu[1] = pwk[0] = pwk[1] = 1;
    for (int i = 2; i <= N - 5; i++){
        pwk[i] = 1ll * pwk[i - 1] * k % P;
        if (!flag[i]) pr[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * pr[j] <= N - 5; j++){
            flag[i * pr[j]] = 1;
            if (i % pr[j] == 0){
                mu[i * pr[j]] = 0;
                break;
            }
            mu[i * pr[j]] = -mu[i];
       }
    }
    for (int i = 1; i <= N - 5; i++) for (int j = i; j <= N - 5; j += i) D[j].push_back(i);
    for (int s = 2; s <= n + n - 2; s++) for (int g : D[s]) for (int d : D[s / g]){
        int l = max(1, s / g - (int)((n - 1) / g)), r = min((int)((n - 1) / g), s / g - 1), t = 1ll * mu[d] * ((int)(r / d) - (int)((l - 1) / d)) % P;
        t = (t + P) % P, ans = (ans + 1ll * t * pwk[max(s - n, g)] % P) % P;
    }
    printf ("%lld\n", 1ll * ans * ksm(pwk[n], P - 2) % P);
    return 0;
}

关于 $cnt = \max(\gcd(i,j),i+j-n)$ 的证明

如果 $i+j\le n$，这个就是弱周期定理。不妨设 $i>j,d=i-j$，考虑归纳法。因为 $i,j$ 都是周期，所以 $\forall x,s_x = s_{x+i} = s_{s+i-j} = s_{x+d}$，所以 $d$ 也是 $s$ 的一个周期。类似于 $\gcd$ 的更相减损法，我们可以归纳证明得到 $\gcd(i,j)$ 是 $s$ 的最小周期，所以就有 $\gcd(i,j)$ 个连通块。

如果 $i+j>n$，就只会有 $n-j$ 条边。假设有 $tot$ 个环，那么就有 $i-(n-j)+tot$ 个连通块，也就是 $i+j-n+tot$。我们只要求出 $tot$。利用周期的性质，我们容易得到 $tot = \max(n-i-j+\gcd(i,j),0)$。

综上所述，$cnt = \max(\gcd(i,j),i+j-n)$。