CF1139D Steps to One(期望DP+容斥+数论)

题目链接

题意：





题解：

AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double,double> pdd;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};

ll n,dp[maxn];
vector<ll> d[maxn],cnt[maxn];
ll Pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
//逆元
ll inv(ll b){
    return Pow(b,mod-2)%mod;
}
void init(){
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            d[j].pb(i),cnt[j].pb(0);
    for(int i=1;i<=n;i++)
        for(int j=d[i].size()-1;j>=0;j--){
            cnt[i][j]=n/d[i][j];
            for(int k=j+1;k<d[i].size();k++)
                if(d[i][k]%d[i][j]==0)cnt[i][j]-=cnt[i][k];
        }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n;
    init();
    dp[1]=0;
    for(int i=2;i<=n;i++){
        ll x=0,y=0;
        for(int j=0;j<d[i].size();j++){
            if(d[i][j]==i)y=(y+cnt[i][j])%mod;
            else x=(x+dp[d[i][j]]*cnt[i][j]%mod)%mod;
        }
        y=(n-y+mod)%mod;
        x=(x+n)%mod;
        dp[i]=x*inv(y)%mod;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans=(ans+dp[i]+1)%mod;
    cout<<ans*inv(n)%mod;
    return 0;
}