题解 CF1139D 【Steps to One】
George1123
·
·
题解
更好的体验\to \color{#142857}{\it George1123}。
题面
CF1139D Steps to One
一个数列，每次随机选一个 [1,m] 之间的数加在数列末尾，数列中所有数的 \gcd=1 时停止，求期望长度 \bmod 10^9+7。
数据范围：1\le m\le 10^5。
蒟蒻语
这题的非 dp 做法讲得太玄了而且写题解的人貌似不屑于解释，于是蒟蒻来写一篇。
蒟蒻解
先推一波概率期望式（E(x) 是 x 的期望，P(x) 是 x 事件的概率）。
\begin{aligned}
E(len)=&\sum_{i\ge 1}P(len=i)\cdot i\\
=&\sum_{i\ge 1}P(len=i)\sum_{j=1}^i\\
=&\sum_{j\ge 1}\sum_{i\ge j}P(len=i)\\
=&\sum_{i\ge 1}P(len\ge i)\\
=&1+\sum_{i\ge 1}P(len>i)\\
\end{aligned}
因为 \gcd_{i=1}^{len} a_i=1 就结束了，所以：
\begin{aligned}
P(len>i)=&P\left(\left(\gcd_{j=1}^{i} a_i\right)>1\right)\\
=&1-P\left(\left(\gcd_{j=1}^{i} a_i\right)=1\right)\\
=&1-\frac{\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots\sum_{a_i=1}^m\epsilon\left(\left(\gcd_{j=1}^{i} a_i\right)\right)}{m^i}\\
=&^{\color{#aa88cc}{(1)}}1-\frac{\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots\sum_{a_i=1}^m\sum_{d|\left(\gcd_{j=1}^{i} a_i\right)}\mu(d)}{m^i}\\
=&1-\frac{\sum_{d=1}^m\mu(d)\sum_{a_1=1}^m[d|a_1]\sum_{a_2=1}^m[d|a_2]\cdots\sum_{a_i=1}^m[d|a_i]}{m^i}\\
=&1-\frac{\sum_{d=1}^m\mu(d)\left(\lfloor\frac{m}{d}\rfloor\right)^i}{m^i}\\
=&^{\color{#eeaa22}{(2)}}-\frac{\sum_{d=2}^m\mu(d)\left(\lfloor\frac{m}{d}\rfloor\right)^i}{m^i}\\
\end{aligned}
带回上式：
$$
\begin{aligned}
E(len)=&1+\sum_{i\ge 1}P(len>i)\\
=&1-\sum_{i\ge 1}\frac{\sum_{d=2}^m\mu(d)\left(\lfloor\frac{m}{d}\rfloor\right)^i}{m^i}\\
=&1-\sum_{i\ge 1}\frac{1}{m^i}\sum_{d=2}^m\mu(d)\left(\lfloor\frac{m}{d}\rfloor\right)^i\\
=&1-\sum_{d=2}^m\mu(d)\sum_{i\ge 1}\left(\frac{\lfloor\frac{m}{d}\rfloor}{m}\right)^i\\
=&^{\color{#ff2211}{(3)}}1-\sum_{d=2}^m\mu(d)\frac{\lfloor\frac{m}{d}\rfloor}{m-\lfloor\frac{m}{d}\rfloor}\\
\end{aligned}
$$
$\color{#ff2211}{(3)}$ 是无穷等比数列求值：
$$s=x+x^2+x^3+\cdots$$
$$sx=x^2+x^3+x^4+\cdots$$
$$s-sx=x$$
$$s=\frac{x}{1-x}$$
然后就可以筛个 $\mu(i)$ 就可以 $\Theta(m)$ 地算了，当然您可以杜教到 $\Theta(m^{\frac 23})$，但是那么秀有什么意思呢……
---
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair((a),(b))
#define x first
#define y second
#define be(a) (a).begin()
#define en(a) (a).end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define R(i,a,b) for(int i=(a),I=(b);i<I;i++)
#define L(i,a,b) for(int i=(a),I=(b);i>I;i--)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int mod=1e9+7;
//Sieve
struct sieve{
int n;
vector<bool> np;
vector<int> prime,mu,inv;
void Sieve(){
np[1]=true,mu[1]=1;
R(i,2,n){
if(!np[i]) prime.pb(i),mu[i]=-1;
for(int p:prime){
if(!(i*p<n)) break;
np[i*p]=true;
if(i%p==0){mu[i*p]=0;break;}
mu[i*p]=mu[i]*mu[p];
}
}
inv[1]=1;
R(i,2,n) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
sieve(int _n){
n=_n,np.assign(n,false),inv.resize(n);
prime.clear(),mu.resize(n),Sieve();
}
};
//Main
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n; cin>>n;
sieve math(n+1);
int ans=1;
R(i,2,n+1) (ans+=mod-1ll*(mod+math.mu[i])%mod
*(n/i)%mod*math.inv[n-n/i]%mod)%=mod;
cout<<ans<<'\n';
return 0;
}
```
---
**祝大家学习愉快！**