Sol
设 $len$ 为随机出来的一个序列长度。
$$E(len) = \sum\limits_{i \geq 1} P(len = i) \times i$$
$$E(len) = \sum\limits_{i \geq 1} P(len = i) \sum\limits_{j=1}^{i} 1$$
$$E(len) = \sum\limits_{j \geq 1} \sum\limits_{i \geq j} P(len = i) = \sum\limits_{i \geq 1} P(len \geq i) = 1 + \sum\limits_{i \geq 1} P(len > i)$$
现在来处理后面的 $\sum\limits_{i \geq 1} P(len > i)$
$$P(len > i) = P((gcd_{j=1}^{i} a_i) > 1)$$
阴阳师:“正难则反”
$$P(len > i) = 1 - P((gcd_{j=1}^{i} a_i) = 1)$$
对于序列中的每一个数,其实都可以枚举它们是 $[1,m]$ 中的哪一个,再除掉 $m^i$ 为 $i$ 个球放在 $m$ 个标有数字的盒子中,且允许有数字没出现过的总方案数。
$$lsh = \frac{\sum_{a_1 = 1}^{m}\sum_{a_2 = 1}^{m}\cdots \sum_{a_{i} = 1}^{m} \epsilon(gcd_{j=1}^{i} a_j)}{m^i} $$
对最后一层的求和符号使用莫比乌斯反演
$$lsh = \frac{\sum_{a_1 = 1}^{m}\sum_{a_2 = 1}^{m}\cdots \sum_{a_{i} = 1}^{m}\sum_{d|(gcd_{j = 1}^{i} a_j)} \mu(d)}{m^i} $$
对每一层都莫比乌斯反演,把枚举的 $d$ 提到最前面去
$$lsh = 1 - \frac{\sum_{d=1}^{m} \mu(d)\sum_{a_1=1}^{m} [d|a_1] \cdots}{m^i}$$
后面的部分上指标同时除以 $d$ 之后可以直接拿出来
$$lsh = \frac{\sum_{d=1}^{m} \mu(d) (\lfloor \frac{m}{d} \rfloor)^i}{m^i}$$
$$lsh = 1 - \frac{\sum_{d=2}^{m} \mu(d) (\lfloor \frac{m}{d} \rfloor)^i}{m^i}$$
所以带回原式可得:
$$1 - \frac{1}{m^i} \sum\limits_{i \geq 1}\sum\limits_{d=2}^{m} \mu(d)(\lfloor \frac{m}{d} \rfloor)^i$$
整除分块:
$$1-\sum\limits_{d = 2}^{m} \mu(d)\frac{\lfloor \frac{m}{d} \rfloor}{m - \lfloor \frac{m}{d} \rfloor}$$
马老师告诉你,后面那一坨类似于杜教筛预处理即可。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int SIZE = 2e5 + 5;
const int mod = 1e9 + 7;
int m, tot;
int isnPri[SIZE], pri[SIZE], mu[SIZE], inv[SIZE];
namespace GTR {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (c < 48 || c > 57) b ^= c == '-', c = fetch();
while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
return b ? a : -a;
}
} using GTR::read;
int qPow(int a, int b) {
int ans = 1ll;
for ( ; b; b >>= 1, a = a * a % mod) {
if (b & 1) ans = ans * a % mod;
}
return ans % mod;
}
void init() {
isnPri[1] = mu[1] = 1;
for (int i = 2; i <= m + 1; ++ i) {
if (!isnPri[i]) pri[++ tot] = i, mu[i] = -1;
for (int j = 1; j <= tot && i * pri[j] <= m + 1; ++ j) {
isnPri[i * pri[j]] = 1;
if (i % pri[j]) mu[i * pri[j]] = -mu[i];
else { mu[i * pri[j]] = 0; break; }
}
}
inv[1]=1;
for (int i = 2; i <= m + 1; ++ i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
signed main() {
m = read(); init();
int ans = 1ll;
for (int i = 2; i <= m + 1; ++ i) ans = (ans - (mu[i] * (m / i) % mod * inv[m - m / i] % mod) + mod) % mod;
printf("%lld\n", ans % mod);
return 0;
}