Codeforces 1097D (期望DP + 积性函数 + 质因子独立)

Codeforces 1097D
题意：给定 $n,k$，一共会进行 $k$ 次操作，每次操作会把 $n$ 等概率的变成 $n$ 的某个约数
求操作 $k$ 次后 $n$ 的期望是多少

考虑到质因子的概率是独立的，那么我们只需要解出$n=p^k$的期望即可。
考虑设$dp(i, j)$为$p^i$操作$j$次的期望，那么
$$
dp(i,j)=\sum_{k=0}^i\frac{1}{i+1} dp(k,j-1)
$$
然后分解质因数乘起来即可。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MO = 1e9 + 7;

    LL n, k, ans = 1, dp[60][10000 + 5];

    LL ksm(LL a, LL b) {
        LL ans = 1, bs = a % MO;
        while (b) {
            if (b & 1) ans = ans * bs % MO;
            bs = bs * bs % MO;
            b >>= 1;
        }
        return ans;
    }

    LL dfs(LL &a, LL i, LL j) {
        if (i == 0) return dp[i][j] = 1;
        if (j == 0) return dp[i][j] = ksm(a, i);
        if (dp[i][j] >= 0) return dp[i][j];
        LL ret = 0;
        for (LL k = 0; k <= i; ++k) (ret += dfs(a, k, j - 1)) %= MO;
        return dp[i][j] = ret * ksm(i + 1, MO - 2) % MO;
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> k;
        for (LL i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                LL cnt = 0;
                while (n % i == 0) n /= i, ++cnt;
                ms(dp, -1);
                ans = ans * dfs(i, cnt, k) % MO;
            }
        }
        ms(dp, -1);
        if (n != 1) ans = ans * dfs(n, 1, k) % MO;
        cout << ans;

        return 0;
    }  
}
int main() {
    flyinthesky::solve();
    return 0;
}