Codeforces 1097D Makoto and a Blackboard
题目链接
http://codeforces.com/contest/1097/problem/D
题目大意
给你一个数 $n$，对它进行 $k$ 次操作，每次将它变为一个它的因数。假定每次变换都是等概率的，问最后剩下的数期望是多少。
题目分析
首先考虑使用 $DP$ 来解决这道题，式子还是比较好推的，有
$$f[0][n] = 1$$ $$f[i][n] = \sum\limits_{j | n}{f[i – 1][j] * \frac{1}{d(j)}}$$
但是这个 $DP$ 的复杂度是 $O(kd ^ 2(n))$ 的显然无法满足题意。
继续观察题目，可以注意到，任何两个不同的质因子之间其实是互不影响的。例如，$3$ 的期望剩余数量显然是不受 $2$ 的数量影响的。由此可知，它是个积性函数。
那么也就是需要将 $n$ 分解质因数为 $n = {p_1} ^ {x_1} {p_2} ^ {x_2} … {p_m} ^ {x_m}$。设 $g(x, k)$ 为 $x$ 执行 $k$ 次操作剩余数的期望，则有 $g(n, k) = \prod\limits_{i = 1}^{m}{g({p_i} ^ {x_i}, k)}$
那么对于求 $g({p_i} ^ {x_i}, k)$，可以用之前讨论的那个 $DP$。在 $n$ 为质数的幂时，该 $DP$ 可使用前缀和将复杂度降低到 $kd(n)$，由此一来，本题即可解决
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
long long n, k;
long long mod = 1e9 + 7;
const int maxn = 2e5 + 5;
const int maxm = 1e7 + 5;
vector <long long> vec;
vector <int> e[maxn];
long long f[2][maxn];
long long inv[maxn];
long long cnt[maxn];
int read(){
int x;
scanf("%d", &x);
return x;
}
long long qpow(long long b, long long x){
long long ret = 1;
while(x){
if(x & 1){
ret = ret * b % mod;
}
b = b * b % mod;
x >>= 1;
}
return ret;
}
int main(){
int i, j, l;
long long x = 1, y = 0;
long long ans = 1;
long long maxx = 0;
cin >> n >> k;
long long tmp = sqrt(n);
for(i=2;i<=tmp;i++){
if(n % i == 0){
vec.push_back(i);
while(n % i == 0){
n /= i;
cnt[vec.size() - 1]++;
}
}
}
if(n > 1){
vec.push_back(n);
cnt[vec.size() - 1] = 1;
}
for(i=1;i<=100;i++){
inv[i] = qpow(i, mod - 2);
}
for(i=0;i<vec.size();i++){
memset(f, 0, sizeof(f));
f[0][cnt[i]] = 1;
for(l=1;l<=k;l++){
long long t = 0;
for(j=0;j<=cnt[i];j++){
f[(l & 1)][j] = 0;
}
for(j=cnt[i];j>=0;j--){
t = (t + f[!(l & 1)][j] * inv[j + 1]) % mod;
f[l & 1][j] = t;
}
}
x = 1;
y = 0;
for(j=0;j<=cnt[i];j++){
y = (y + (x * f[k & 1][j]) % mod) % mod;
x = x * vec[i] % mod;
}
ans = ans * y % mod;
}
cout << ans % mod << endl;
return 0;
}