[人工智能]CF1139D Steps to One 题解

一道莫反好题。

先证个式子：$E(X)={\sum }_{i\ge 1}P(X\ge i)$，也就是最终长度为 $X$ 的期望是所有最终长度小于等于 $X$ 的概率之和。

证明：$E(X)={\sum }_{i\ge 1}iP(X=i)={\sum }_{i\ge 1}{\sum }_{1\le j\le i}P(X=i)={\sum }_{j\ge 1}{\sum }_{i\ge j}P(X=i)={\sum }_{j\ge 1}P(x\ge j)$。

考虑容斥，最终长度大于等于 $i$ 等价于长度为 $i?1$ 的序列 $\gcd$ 大于 1，这个可以用 1 减去 $\gcd =1$ 的概率，注意这里的 $i\ge 2$。

概率用满足条件方案数 / 总方案数计算，总方案数 $m^{i?1}$，因此只需要计算 $i?1$ 时 $\gcd =1$ 的方案数即可。

推 $\gcd =1$ 的式子：${\sum }_{1\le a_1,a_2,...,a_{i?1}\le m}[\gcd (a_1,a_2,...,a_{i?1})=1]$

莫比乌斯反演，得到 ${\sum }_{1\le a_1,a_2,...,a_{i?1}\le m}{\sum }_{d\mid \gcd (a_1,a_2,...,a_{i?1})}\mu (d)$

换个枚举顺序，顺便处理一下求和符号得到 ${\sum }_{d=1}^m\mu (d)?\frac{m}{d}{?}^{i?1}$

然后开始计算答案式子，为 $1+{\sum }_{i\ge 2}\frac{m^{i?1}?{\sum }_{d=1}^m\mu (d)?\frac{m}{d}{?}^{i?1}}{m^{i?1}}$。

$i?1$ 太丑，令 $i\leftarrow i?1$，得到 $1+{\sum }_{i\ge 1}\frac{m^i?{\sum }_{d=1}^m\mu (d)?\frac{m}{d}{?}^i}{m^i}$。

注意到 $d=1$ 时 ${\sum }_{d=1}^m\mu (d)?\frac{m}{d}{?}^i=m^i$，因此将这一部分提出来与 $m^i$ 消掉。

然后交换求和符号，得到 $1?{\sum }_{d=1}^m\mu (d)(\frac{?\frac{m}{d}?}{m}{)}^i$。

因为 $\frac{?\frac{m}{d}?}{m}<1$，根据 $x<1\to {\sum }_{i\ge 1}{x}^i=\frac{x}{1?x}$（貌似是用生成函数推的），得到 $1?{\sum }_{d=1}^m\mu (d)\frac{\frac{?\frac{m}{d}?}{m}}{m?\frac{?\frac{m}{d}?}{m}}$，然后整除分块即可。

GitHub：CodeBase-of-Plozia

Code：

/*
========= Plozia =========
	Author:Plozia
	Problem:CF1139D Steps to One
	Date:2022/3/1
========= Plozia =========
*/

#include <bits/stdc++.h>

typedef long long LL;
const int MAXN = 1e5 + 5;
const LL P = 1e9 + 7;
int t, n, cntPrime, Prime[MAXN];
LL mu[MAXN], inv[MAXN];
bool book[MAXN];

int Read()
{
	int sum = 0, fh = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = sum * 10 + (ch ^ 48);
	return sum * fh;
}
int Max(int fir, int sec) { return (fir > sec) ? fir : sec; }
int Min(int fir, int sec) { return (fir < sec) ? fir : sec; }
LL ksm(LL a, LL b = P - 2, LL p = P)
{
	LL s = 1 % p;
	for (; b; b >>= 1, a = a * a % p)
		if (b & 1) s = s * a % p;
	return s;
}

void init()
{
	book[1] = mu[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		if (!book[i]) { Prime[++cntPrime] = i; mu[i] = -1; }
		for (int j = 1; j <= cntPrime; ++j)
		{
			if (i * Prime[j] > n) break ;
			book[i * Prime[j]] = 1;
			if(i % Prime[j] == 0) { mu[i * Prime[j]] = 0; break ; }
			mu[i * Prime[j]] = -mu[i];
		}
	}
	for (int i = 2; i <= n; ++i) mu[i] = mu[i - 1] + mu[i];
}

int main()
{
	n = Read(); init(); LL ans = 0;
	for (int i = 1; i <= n; ++i) inv[i] = ksm(i);
	for (int l = 2, r; l <= n; l = r + 1)
	{
		r = Min(n / (n / l), n);
		ans = (ans + (mu[r] - mu[l - 1]) * (n / l) % P * inv[n - (n / l)] % P) % P;
	}
	ans = ((1 - ans) % P + P) % P;
	printf("%lld\n", ans);
	return 0;
}