Solution - Makoto and a Blackboard

Link。

朴素 dp 应该不用说了。放个用 map 的代码。

int dfs(int n, int k) {
	if (!k) return n;
	if (f[make_pair(n, k)]) return f[make_pair(n, k)];
	int tot = 0, ans = 0;
	for (int i = 1; i * i <= n; i++) {
		if (n % i) continue;
		ans = (ans + dfs(i, k - 1)) % MOD;
		tot++;
		if (i != n / i) {
			ans = (ans + dfs(n / i, k - 1)) % MOD;
			tot++;
		}
	}
	return f[make_pair(n, k)] = ans * qkpow(tot, MOD - 2) % MOD;
}

然后我期待有什么神秘转化，妙妙思路，结果，，，你告诉我这是个积性函数？？？

Definition.

若函数 \(f(n)\) 满足 \(f(1) = 1\) 且 \(\forall x, y \in \mathbb{N_+}, \gcd(x, y) = 1\) 都有 \(f(xy) = f(x)f(y)\)，则 \(f(n)\) 为积性函数。

以前完全不知道的一个性质。哦好像讲欧拉函数的时候有提过。

证明这个玩意可以感性理解，\(f(x) = \dfrac{a_1 + a_2 + \dots + a_n}{n}, f(y) = \dfrac{b_1 + b_2 + \dots + b_m}{m}\)，然后因为 \(\gcd(x,y) = 1\)，\(a\) 和 \(b\) 除了 \(1\) 应该是没有重复的，\(xy\) 的因数也就是 \(a, b\) 中选出两个的乘积，跟定义是一样的。

然后就分解一下，\(n = p_1 ^ {\alpha_1}p_2 ^ {\alpha_2}\dots p_n ^ {\alpha_n}, p_1 < p_2 < \dots < p_n\)，相当于只需要算质数的次幂结果了。然后因为是质数的次幂，因数也只能是这个质数的次幂，上面的 dp 就是 \(O(\alpha k)\) 的了，最后乘起来即可。

namespace liuzimingc {
const int N = 65, K = 1e4 + 5, MOD = 1e9 + 7;
#define endl '\n'
#define int long long

int n, k, f[N][K], ans = 1, p;

int qkpow(int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return ans;
}

int dfs(int n, int k) { // p ^ n, k
    if (!n) return 1;
	if (!k) return qkpow(p, n);
	if (f[n][k]) return f[n][k];
	int ans = 0;
	for (int i = 0; i <= n; i++)
		ans = (ans + dfs(n - i, k - 1)) % MOD;
	return f[n][k] = ans * qkpow(n + 1, MOD - 2) % MOD;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> k;
	for (p = 2; p * p <= n; p++) {
		if (n % p) continue;
		int tot = 0;
		while (n % p == 0) n /= p, tot++;
		// cout << tot << endl;
		ans = ans * dfs(tot, k) % MOD;
		for (int i = 1; i <= tot; i++)
		    for (int j = 1; j <= k; j++)
		        f[i][j] = 0;
	}
	if (n > 1) {
		p = n;
		ans = ans * dfs(1, k) % MOD;
	}
	cout << ans << endl;
	return 0;
}
#undef int
} // namespace liuzimingc