L3-030 可怜的简单题（2021天梯赛 L3-3）

博主： spirit
发布时间：2021 年 08 月 05 日
2292 次浏览
暂无评论
2906字数
分类：数论概率期望

# L3-030 可怜的简单题（2021天梯赛 L3-3）

[题目链接](https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652366) [参考博客](https://blog.csdn.net/weixin_45697774/article/details/116602998)

首先可以发现，$len(A)$ 是一个随机正整数变量，取值范围 $[1, +\infty]$ ，这类变量有一个性质：

- 假设 $X$ 是一个随机正整数变量，则：$E(X) = \sum_{i = 1}^{\infty}P(x \geq i)$ 。
  $$
  \begin{equation}\begin{split}
  E(x) &= \sum_{k = 1}^{\infty} P(X = k) k \\
  &= \sum_{k = 1}^{\infty} P(X = k) \sum_{i = 1}^{k} 1 \\
  &= \sum_{i = 1}^{\infty} 1 \sum_{k \geq i}^{\infty} P(X = k) \\
  &= \sum_{i = 1}^{\infty} P(X \geq i) \\
  \end{split}\end{equation}
  $$

套用这个性质可以得到：

$$
\begin{equation}\begin{split}
E(len) &= \sum_{i = 1}^{\infty} P(len >= i) \\
&= 1 + \sum_{i = 1}^{\infty} P(len > i) \\
\end{split}\end{equation}
$$

然后考虑 $P(len > i)$ 的值就可以了，直接求不好算，考虑容斥一下：

$$
\begin{equation}\begin{split}
P(len > i) &= 1 - P(len \leq i) \\
&= 1 - \frac{\sum_{a_1 = 1}^{n} \sum_{a_2 = 1}^{n}...\sum_{a_i = 1}^{n} (\gcd_{j = 1}^i a_j = 1)}{n^i} \\
&= 1 - \frac{\sum_{a_1 = 1}^{n} \sum_{a_2 = 1}^{n}...\sum_{a_i = 1}^{n} (\sum_{d | gcd} \mu(d))}{n^i} \\
&= 1 - \frac{\sum_{d = 1}^{n} \mu(d) (\lfloor \frac{n}{d} \rfloor)^i}{n^i} \\
&= - \frac{\sum_{d = 2}^{n} \mu(d) (\lfloor \frac{n}{d} \rfloor)^i}{n^i} \\
\end{split}\end{equation}
$$

代入化简可得：

$$
\begin{equation}\begin{split}
E(len) 
&= 1 - \sum_{i = 1}^{\infty} \frac{\sum_{d = 2}^{n} \mu(d) (\lfloor \frac{n}{d} \rfloor)^i}{n^i} \\
&= 1 - \sum_{d = 2}^{n} \mu(d) \sum_{i = 1}^{\infty} (\frac{(\lfloor \frac{n}{d} \rfloor)}{n})^i \\
&= 1 - \sum_{d = 2}^{n} \mu(d) \frac{\lfloor \frac{n}{d} \rfloor}{n - \lfloor \frac{n}{d} \rfloor} \\
\end{split}\end{equation}
$$

第三个等号的化简：当 $|x| < 1$ 时，有 $S(n) = \sum_{i = 1}^{n} x^i$ ，求 $\lim_\limits{n \to +\infty} S(n)$。

$$
\begin{equation}\begin{split}
S(n) &= x^1 + x^2 + x^3 + ... + x^n \\
xS(n) &= x^2 + x^3 + x^4 + ... + x^{n + 1} \\
(1 - x)S(n) &= x - x^{n + 1} \\
S(n) &= \frac{x - x^{n + 1}}{1 - x} \\
\lim_\limits{n \to +\infty} S(n) &= \frac{x}{1 - x} \\ 
\end{split}\end{equation}
$$

这里令 $x = \frac{(\lfloor \frac{n}{d} \rfloor)}{n}$ ，代入化简即可得到最终结果。

然后就可以用杜教筛求莫比乌斯函数前缀和，再用数论分块计算结果了。

由于模数 $p$ 比较大，需要使用防溢出的乘法或者 `__int128` 强转一下。

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e7 + 5;
int primes[N], cnt;
bool prime[N + 5];
int mu[N + 5];
unordered_map<LL, LL> smu;
LL n, p;

LL mul(LL a, LL b) {
    a %= p, b %= p;
    LL c = (long double)a * b / p;
    LL ans = a * b - c * p;
    if (ans < 0) ans += p;
    else if (ans >= p) ans -= p;
    return ans;
}

LL fastPow(LL a, LL k) {
	LL res = 1;
	while (k) {
		if (k & 1) res = mul(res, a);
		k >>= 1;
		a = mul(a, a) % p;
	}
	return res % p;
}

void init() {
	mu[1] = 1;
	for (int i = 2; i < N; i++) {
		if (!prime[i]) {
			primes[cnt++] = i;
			mu[i] = -1;
		}
		for (int j = 0; primes[j] <= N / i; j++) {
			prime[i * primes[j]] = true;
			if (i % primes[j]) {
				mu[i * primes[j]] = -mu[i];
			} else {
				mu[i * primes[j]] = 0;
				break;
			}
		}
	}
	for (int i = 1; i < N; i++) mu[i] = (mu[i] + mu[i - 1]) % p;
}

LL get_sum_mu(LL n) {
	if (n < N) return mu[n];
	if (smu.count(n)) return smu[n];
	LL ans = 1;
	for (LL l = 2, r; l <= n; l = r + 1) {
		r = min(n, n / (n / l));
		ans -= (r - l + 1) * get_sum_mu(n / l);
	}
	ans = (ans % p + p) % p;
	return smu[n] = ans;
}

int main() {
	scanf("%lld %lld", &n, &p);
	init();
	LL res = 1;
	for (LL l = 2, r; l <= n; l = r + 1) {
		r = min(n, n / (n / l));
		res = (res - mul((get_sum_mu(r) - get_sum_mu(l - 1)), mul((n / l) % p, 
			fastPow((n - n / l) % p, p - 2)))) % p;
	}
	res = (res % p + p) % p;
	cout << res << '\n';
	return 0;
}
```

最后修改：2022 年 04 月 03 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

L3-030 可怜的简单题（2021天梯赛 L3-3）

spirit • 2021 年 08 月 05 日

# L3-030 可怜的简单题（2021天梯赛 L3-3）

[题目链接](https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652366) [参考博客](https://blog.csdn.net/weixin_45697774/article/details/116602998)

首先可以发现，$len(A)$ 是一个随机正整数变量，取值范围 $[1, +\infty]$ ，这类变量有一个性质：

套用这个性质可以得到：

$$
\begin{equation}\begin{split}
E(len) &= \sum_{i = 1}^{\infty} P(len >= i) \\
&= 1 + \sum_{i = 1}^{\infty} P(len > i) \\
\end{split}\end{equation}
$$

然后考虑 $P(len > i)$ 的值就可以了，直接求不好算，考虑容斥一下：

代入化简可得：

第三个等号的化简：当 $|x| < 1$ 时，有 $S(n) = \sum_{i = 1}^{n} x^i$ ，求 $\lim_\limits{n \to +\infty} S(n)$。

这里令 $x = \frac{(\lfloor \frac{n}{d} \rfloor)}{n}$ ，代入化简即可得到最终结果。

然后就可以用杜教筛求莫比乌斯函数前缀和，再用数论分块计算结果了。

由于模数 $p$ 比较大，需要使用防溢出的乘法或者 `__int128` 强转一下。

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e7 + 5;
int primes[N], cnt;
bool prime[N + 5];
int mu[N + 5];
unordered_map<LL, LL> smu;
LL n, p;

LL mul(LL a, LL b) {
    a %= p, b %= p;
    LL c = (long double)a * b / p;
    LL ans = a * b - c * p;
    if (ans < 0) ans += p;
    else if (ans >= p) ans -= p;
    return ans;
}

LL fastPow(LL a, LL k) {
	LL res = 1;
	while (k) {
		if (k & 1) res = mul(res, a);
		k >>= 1;
		a = mul(a, a) % p;
	}
	return res % p;
}

L3-030 可怜的简单题（2021天梯赛 L3-3）

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Kattis Message （状态机模型 + 矩阵快速幂）

数论进阶——莫比乌斯反演

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

Kattis Fruit Slicer （计算几何 + 扫描线）

Kattis Terraced fields （数位DP）

杜教筛

堆的实现

L3-030 可怜的简单题（2021天梯赛 L3-3）

线性DP入门

L3-030 可怜的简单题（2021天梯赛 L3-3）

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

L3-030 可怜的简单题（2021天梯赛 L3-3）

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款