【题解】Makoto and a Blackboard 概率 dp CF1097D ——quhengyi11

click here!

题目大意就是给一个 n，每次操作能将 n 等概率变成它的一个因数，求 k 次操作后的期望

比赛的时候想到质因数分解了，然而还是因为概率 dp 太弱没打出来

我们先考虑数 $p^{cnt}$的答案

设 $f_{i,j}$表示第 $i$次操作后 $p^j$为当前数的概率

我们容易知道 $f_{0,cnt}=1$

我们根据题目容易写出转移方程

$$f_{i,j}=\sum_{k=j}^{cnt} \frac {f_{i-1, k}} {k+1}$$

表示的就是由前驱状态转移过来的概率

容易发现

$$f_{i, j+1}=\sum_{k=j+1}^{cnt} \frac {f_{i-1, k}} {k+1}$$

所以有

$$f_{i,j}=f_{i, j+1}+\frac{f_{i-1,j}}{j+1}$$

因此我们可以用 $O(n\times cnt)$的时间复杂度递推出 $f$，然后和贡献乘一下就是期望了

对于一个 $n=\prod p_i^{a_i}$

我们容易发现每个因数的期望是独立的，事实上想想期望的线性性就明白了，或者在脑子里把式子展开你会发现是等价的

因此我们分解质因数之后做上述操作，并把答案相乘即可

时间复杂度 $O(\sqrt n + nlogn)$

为了复习一下线性求逆元 (这东西忘记了真的有点难想)，这里再写一遍证明吧（尽管这道题不一定要用，但是我的代码里还是用了下（：不会的 dalao 可以跳过这一段直接看代码了呢

设 $p$为模数，已知 $inv_{1\cdots i-1}$求 $inv_i$

设 $k=p/i,r=p\%i$
$$
\begin{align}
p&=ki+r\\
0&=ki+r\quad(mod\;p)\\
0&=k\times inv_r+inv_i\quad(mod\;p)\\
inv_i&=-k\times inv_r \quad(mod\;p)\\
inv_i&=(p-p/i)\times inv_{p\%i} \quad(mod\;p)
\end{align}
$$

代码 (某些部分有点毒瘤)

#include<bits/stdc++.h>
#define fo(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fd(i, a, b) for (ll i = (a); i >= (b); --i)
#define mod 1000000007
#define N 10005
#define ll long long
ll n, f[N][66], inv[66], ans, po[66], sq;
int k;
int main ()
{
    scanf("%lld %d", &n, &k);
    sq = std::min(n, (ll) (sqrt(n) + 1));
    inv[1] = 1;
    fo (i, 2, 65) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    ans = 1;
    fo (p, 2, sq)
    {
        if (n % p == 0)
        {
            int cnt = 1;
            n /= p;
            while (n % p == 0) ++cnt, n /= p;
            memset(f[0], 0, sizeof f[0]);
            f[0][cnt] = 1; po[0] = 1;
            fo (i, 1, cnt) po[i] = po[i - 1] * p % mod;
            fo (i, 1, k)
            {
                f[i][cnt + 1] = 0;
                fd (j, cnt, 0)
                    f[i][j] = (f[i][j + 1] + f[i - 1][j] * inv[j + 1]) % mod;
            }
            ll now = 0;
            fo (j, 0, cnt)
                now = (now + f[k][j] * po[j]) % mod;
            ans = ans * now % mod;
        }
        if (p == sq && n > 1) 
            p = n - 1, sq = n;
    }
    printf("%lld\n", ans);
    return 0;
}