题目大意
序列每次随机添加一个 \([1,m]\) 的整数,直到序列 \(gcd=1\) 停止,求期望操作次数。
分析
模拟过程发现只关心整个序列的 \(gcd\) 与下一次会添加什么,那么根据期望 \(dp\) 套路可得状态 \(f_{i}\) 表示当前序列 \(gcd=i\),期望还操作多少次使得 \(gcd=1\)。
考虑枚举下一个数,转移方程有:
解方程得:$$f_{i}=\frac{m+\sum\limits_{k=1,k\neq i}^mf_{gcd(i,k)}}{m-\lfloor\frac{m}{i}\rfloor}$$
看到有 gcd 形式,考虑莫比乌斯反演。
反演得:
\[\sum\limits_{j=1}^m [gcd(i,j)=d]=\sum\limits_{x|\lfloor\frac{i}{d}\rfloor}\mu(x)\lfloor\frac{\lfloor\frac{m}{x}\rfloor}{d}\rfloor \]答案为 \(1+\frac{1}{m}\sum\limits_{i=1}^m f_i\)。
时间复杂度近似 \(O(n\sqrt{n})\)
代码
int m,invm,f[N],mu[N],vis[N],inv[N];
vector <int> fac[N],prime;
void init(int n){
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i)
fac[j].pb(i);
mu[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]) mu[i]=mod-1,prime.pb(i);
for(int j=0;prime[j]<=n/i;j++){
vis[i*prime[j]]=1,mu[i*prime[j]]=(i%prime[j]==0?0:mod-mu[i]);
if(i%prime[j]==0) break;
}
}
inv[1]=inv[0]=1;
for(int i=2;i<=n;i++)
inv[i]=mod-(mod/i)*inv[mod%i]%mod;
}
void Main(){
f[1]=0,m=rd;
for(int i=2;i<=m;i++){
for(int d:fac[i]){
if(d==i) break;
int sum=0;
for(int x:fac[i/d])
sum=(sum+mu[x]*(m/x/d)%mod)%mod;
f[i]=(f[i]+sum*f[d]%mod)%mod;
}
f[i]=(f[i]+m)%mod*inv[m-m/i]%mod;
}
int ans=0;
for(int i=1;i<=m;i++)
ans=(ans+f[i])%mod;
ans=(ans*inv[m]%mod+1)%mod;
cout<<ans<<endl;
}
signed main(){
init(N-10);
int T=1;//rd;
while(T--) Main();
}
标签:lfloor,frac,gcd,limits,sum,CodeForces,rfloor,1139D
From: https://www.cnblogs.com/smilemask/p/18312295