Codeforces Round #548 (Div. 2) D 期望dp + 莫比乌斯反演

https://codeforces.com/contest/1139/problem/D

题意

每次从1,m中选一个数加入队列,假如队列的gcd==1停止,问队列长度的期望

题解

• 概率正着推,期望反着推

  发现每加入一个数,gcd会变为原来gcd的因数

  • \(dp[x]\) - > \(dp[gcd(x,i)]\)
  • 但是方程却是反方向的

• 图片

代码

#include<bits/stdc++.h>
#define MOD 1000000007
#define MAXN 100005
#define ll long long 
using namespace std;
ll m,inv,ans,dp[MAXN],i;
vector<int>G[MAXN];
int mu[MAXN],pr[MAXN],cnt,vi[MAXN];
ll pw(ll bs,ll x){
    ll ans=1;
    while(x){
        if(x&1)ans=ans*bs%MOD;
        bs=bs*bs%MOD;
        x>>=1;
    }
    return ans;
}

void get_mu(){
    mu[1]=1;
    for(int i=2;i<MAXN;i++){
        if(!vi[i]){mu[i]=-1;pr[++cnt]=i;}
        for(int j=1;j<=cnt&&pr[j]*i<MAXN;j++){
            vi[i*pr[j]]=1;
            if(i%pr[j]==0)break;
            mu[i*pr[j]]=-mu[i];
        }
    }
}

void sol(){
    dp[1]=0;
    for(int i=2;i<=m;i++){
        dp[i]=m;
        for(int j=0;j<G[i].size();j++){
            ll cnt=0,x=G[i][j];
            if(x==i)continue;
            for(int k=0;k<G[i/x].size();k++){
                ll tp=G[i/x][k];
                cnt+=mu[tp]*(m/x/tp)%MOD;cnt%=MOD;
                cnt+=MOD;
                cnt%=MOD;
            }
            dp[i]+=dp[x]*cnt%MOD;
            dp[i]%=MOD;
        }
        dp[i]=dp[i]*pw((m-m/i)%MOD,MOD-2)%MOD;
    }
}
int main(){
    get_mu();
    cin>>m;
    inv=pw(m,MOD-2);
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j+=i)
            G[j].push_back(i);
    sol();  
    for(int i=1;i<=m;i++){
        ans+=dp[i]%MOD;
        ans%=MOD;
    }
    ans=ans*inv%MOD;
    ans++;
    cout<<ans%MOD;
}

Codeforces Round #548 (Div. 2) D 期望dp + 莫比乌斯反演

原文：https://www.cnblogs.com/VIrtu0s0/p/10597490.html