【题解】Steps to One 概率 dp CF1139D ——quhengyi11

QwQ

这道题思路还算是比较好想.jpg

但是有些细节的东西比如证明复杂度我感觉我特别是 CF 比赛的时候不可能静下心来想到的

好吧我们讲题解

题解

首先我们设 $dp_x$表示 $gcd$到 $x$的时候还要期望 $dp_x$次才能到 $1$

显然 $dp_1=0$

对于 $x\geq 2$，我们有

$$dp_x=1+\sum_{y=1}^m \frac {dp_{gcd(x,y)}}{n}$$

然后你可以建一张图然后跑高斯消元

然后你可以发现我们可以枚举 $gcd$

$$dp_x=1+\sum_{d|x} \frac{f_{x,d}dp_d}{n}$$

这里 $f_{x,d}=\sum_{y=1}^m [gcd(x,y)==d]$

上面的递推式在 $f$已知的情况下已经可以 $O(nlogn)$求解了。

考虑如何预处理 $f$

我们可以假设我们已经处理出了 $f_{x,d+1}$到 $f_{x,dmax}$，现在需要求 $f_{x,d}$

显然我们知道 $\frac m d = \sum_{y=1}^m[gcd(x,y) == kd]$，这里 $k\in N_+$

我们再将它减去 $f_{x,2d},f_{x,3d}…$就可以求出 $f_{x,d}$了

我们记 $d_x$表示 $x$的因数个数

$d_1+…+d_n=nlogn$

我们的复杂度为 $d_1^2+…+d_n^2$，由均值不等式得时间复杂度为 $O(nlog^2n)$

当然我们这里也可以用莫比乌斯反演来做，但是时间复杂度貌似也是两个 $log$的 (不过貌似常数小很多)

代码

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mod 1000000007
#define eps 1e-4
#define N 100005
using std::vector;
int n;
ll dp[N], ans, invn;
vector<int> d[N], f[N];
inline void sieve ()
{
    fo (i, 1, n)
    {
        for (int j = i; j <= n; j += i)
            d[j].pb(i);
        std::reverse(d[i].begin(), d[i].end());
    }
    fo (i, 1, n)
    {
        int sz = d[i].size() - 1;
        fo (j, 0, sz)
        {
            int now = n / d[i][j];
            fo (k, 0, j - 1)
            {
                if (!(d[i][k] % d[i][j]))
                    now -= f[i][k];
            }
            f[i].pb(now);
        }
    }
}
inline ll pow (ll x, int y)
{
    ll ret = 1;
    while (y)
    {
        if (y & 1) ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
int main ()
{
    scanf("%d", &n);
    sieve();
    invn = pow(n, mod - 2);
    fo (i, 2, n)
    {
        int sz = d[i].size() - 1;
        dp[i] = 1;
        fo (j, 1, sz)
            (dp[i] += dp[d[i][j]] * f[i][j] % mod * invn) %= mod;
        dp[i] = dp[i] * pow((1 - f[i][0] * invn % mod + mod) % mod, mod - 2) % mod;
    }
    ans = 1;
    fo (i, 1, n) (ans += dp[i] * invn) %= mod;
    printf("%lld", ans);
    return 0;
}