CodeForces 1139D Steps to One（期望DP + 容斥原理）

大致题意：一个数列，一开始是空的，每次往他最后一个位置随机的加上一个[1,m]范围内的数字，然后对当前数列所有的数字求gcd，如果gcd不为1，那么就继续添加，否则停止。问最后这个数列期望的长度。

这是一个比较明显的期望dp。我们考虑dp[i]表示初始gcd为i的时候也即数列的第一个数字为i的时候，这个数列的期望长度。显然，有转移方程：

整理一下有：

其中的x表示使得gcd(i,y)==j的y的个数。显然这个x是要容斥的。容斥的话，按照最简单的dfs容斥即可，然而我却不要脸的写(wang)错(le)了……好好复习吧，毕竟还没有完全退役。具体见代码：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define file(x) freopen(#x".in","r",stdin);
using namespace std;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

vector<int> num;
LL dp[N],ret;
int m;

LL qpow(LL x,LL n)
{
    LL res=1;
    while(n)
    {
        if(n&1) res=res*x%mod;
        x=x*x%mod; n>>=1;
    }
    return res;
}

void dfs(int dep,LL n,bool flag,LL m)
{
    if (n>m) return;
    if (dep>=num.size()) return;
    if (flag) ret+=m/n; else ret-=m/n;
    for(int i=dep+1;i<num.size();i++)
        dfs(i,n*num[i],flag^1,m);
}

LL cal(int n,int x)
{
    LL res=m/x;
    LL y=n/x; num.clear();
    for(int i=2;i*i<=y;i++)
    {
        if (y%i) continue;
        num.push_back(i);
        while(y%i==0) y/=i;
    }
    if (y>1) num.push_back(y);
    ret=0;
    for(int i=0;i<num.size();i++)
        dfs(i,num[i],0,res);
    return res+ret;
}

int main()
{
    sc(m);
    LL ans,inv;
    dp[1]=ans=1;
    inv=qpow(m,mod-2);
    for(int i=2;i<=m;i++)
    {
        dp[i]=1;
        int x=(LL)m*qpow(m-m/i,mod-2)%mod;
        for(int j=2;j*j<=i;j++)
        {
            if (i%j) continue;
            dp[i]=(dp[i]+cal(i,j)*inv%mod*dp[j]%mod)%mod;
            if (j*j!=i) dp[i]=(dp[i]+cal(i,i/j)*inv%mod*dp[i/j]%mod)%mod;
        }
        dp[i]=dp[i]*x%mod;
    }
    for(int i=2;i<=m;i++)
        ans=(ans+dp[i]*inv%mod)%mod;
    printf("%lld\n",ans);
    return 0;
}