Codeforces

Luogu

分析

容易想到设 $dp_{i,j}$ 表示 $j$ 次操作后 $i$ 的期望大小，转移直接枚举约数即可。然而这样子显然是会 T 的...

注意到当 $\gcd(i,j)=1$ 时有 $dp_{i\times j,k}=dp_{i,k}\times dp_{j,k}$，因此我们可以将 $n$ 分解为 $p_1\!^{c_1}p_2\!^{c_2}\cdots$ 的形式，然后将每个 $dp_{p_i\!^{c_i},k}$ 乘起来即可。

考虑如何计算 $dp_{p_i\!^{c_i},k}$ 。设 $f_{i,j}$ 表示 $j$ 次操作后 $p^i$ 的期望大小，转移时同样枚举约数。由于 $p^i$ 的约数仅有 $i+1$ 个，所以就能跑过去了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1e9+7;
inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,k;
int dp[60][10010];

inline int dfs(int p,int c,int k) {
    if (dp[c][k]) return dp[c][k];
    if (!c) return dp[c][k]=1;
    if (!k) return dp[c][k]=qpow(p,c);
    for (re int i=0;i<=c;++i)
        dp[c][k]=(dp[c][k]+dfs(p,i,k-1))%mod;
    return dp[c][k]=1ll*dp[c][k]*qpow(c+1,mod-2)%mod;
}

signed main() {
    n=read(),k=read(); int ans=1;
    for (re int i=2,c;i*i<=n;++i) {
        if (n%i) continue;
        for (c=0;n%i==0;++c,n/=i);
        memset(dp,0,sizeof(dp));
        ans=1ll*ans*dfs(i,c,k)%mod;
    }
    if (n>1) {
        memset(dp,0,sizeof(dp));
        ans=1ll*ans*dfs(n,1,k)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}