正題

題目鏈接:https://www.luogu.com.cn/problem/CF1139D

---

題目大意

不停的在表格中填下$1～m$中隨機一個數，直到所有數的$gcd=1$為止，求期望數的個數。

---

解題思路

設$f_n$表示現在$gcd$為$n$時的期望個數。那么有轉移方程$$f_n=\frac{{\sum }_{i=1}^m{f}_{gcd(i,n)}}{m}+1$$
為了方便，我們先把其中$?\frac{m}{n}?$個$gcd(i,n)=n$的提出來，我們在后面的計算中均以其為$0$。
如果我們求出一個函數$h(x)={\sum }_{i=1}^m[gcd(i,n)==x]$那么方程就可以轉換成方便的形式，因為顯然只有$x|n$時$h(x)$才有值。

考慮如何求這個$h$，直接上莫反$$H(x)=\sum _{x|d}h(d)=?\frac{m}{x}??[x|n]$$
$$ans=\sum _{x|n}h(x)f_x=\sum _{x|n}{f}_x\sum _{x|y}H(y)\mu (\frac{y}{x})=\sum _{x|n}{f}_x\sum _{x|y,y|n}?\frac{m}{x}?\mu (\frac{y}{x})$$
這個很麻煩計算，把$y$提出來
$$?\sum _{y|n}?\frac{m}{x}?\sum _{x|y}\mu (\frac{y}{x})f_x$$
后面那個做完一個$f$就預處理一個，然后跟著轉移即可。

時間復雜度$O(m\sqrt{m})$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10,P=1e9+7; ll m,cnt,pri[N],mu[N],f[N],g[N]; bool v[N]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } void prime(){mu[1]=1;for(ll i=2;i<=m;i++){if(!v[i])pri[++cnt]=i,mu[i]=-1;for(ll j=1;j<=cnt&&i*pri[j]<=m;j++){v[i*pri[j]]=1;if(i%pri[j]==0)break;mu[i*pri[j]]=mu[i]*mu[pri[j]];}}return;} signed main() {scanf("%lld",&m);prime();ll ans=f[1]=g[1]=1;for(ll n=2;n<=m;n++){for(ll i=1;i*i<=n;i++)if(n%i==0){if(i*i!=n)(g[n]+=mu[i]*f[n/i]%P)%=P;(g[n]+=mu[n/i]*f[i]%P)%=P;}for(ll i=1;i*i<=n;i++)if(n%i==0){if(i*i!=n)(f[n]+=(m/(n/i))*g[n/i]%P)%=P;(f[n]+=(m/i)*g[i]%P)%=P;}f[n]=(f[n]+m)%P*power(m-m/n,P-2)%P;ans=(ans+f[n])%P;(g[n]+=f[n])%=P;}ans=ans*power(m,P-2)%P;printf("%lld\n",(ans+P)%P);return 0; }

總結

以上是生活随笔為你收集整理的CF1139D-Steps to One【期望dp,莫比乌斯反演】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。