题解 CF1097D 【Makoto and a Blackboard】
ouuan
2019-01-06 13:29:19
这里是复杂度为 $O(\sqrt n+k\log n)$ 的做法，很多人都是 $O(\sqrt n+k\log^2 n)$ 的。
先考虑 $n=p^{\alpha}$ 怎么做。 令 $f_{i,j}$ 表示已经操作了 $i$ 次，剩下的数为 $p^j$ 的概率。
那么，$f_{i,j}=\sum\limits_{t=j}^\alpha\frac{f_{i-1,t}}{t+1}$，因为对于每个 $f_{i-1,t}$ 都有 $\frac1{t+1}$ 的概率转移到 $f_{i,j}(0\le j\le t)$ 。
观察这个式子，可以发现，$f_{i,j}=f_{i,j+1}+\frac{f_{i-1,j}}{j+1}$，于是可以 $O(\alpha k)$ 计算出 $f_{k,0..\alpha}$，答案就是 $\sum\limits_{j=0}^\alpha f_{k,j}\times p^j$。
如何扩展到任意的 $n$ 呢？可以发现，对于每个质因数，每次操作减去多少个该质因数是概率独立的，所以可以分开计算然后乘起来。
使用滚动数组可以将空间复杂度优化至 $O(\log n)$（质因数个数）。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=100010;
const int M=1000000007;
int qpow(int x,int y);
ll n;
int k,p[60][2],tot,q=1,ans=1,f[60],inv[60];
int main()
{
int i,j,temp,sum;
cin>>n>>k;
for (i=1;i<60;++i) //预处理逆元
{
inv[i]=qpow(i,M-2);
}
for (i=2;1ll*i*i<=n;++i) //分解质因数
{
if (n%i==0)
{
p[++tot][0]=i;
while (n%i==0)
{
++p[tot][1];
n/=i;
}
}
}
if (n>1)
{
p[++tot][0]=n%M;
p[tot][1]=1;
}
for (;tot;--tot) //对每个质因数分别dp
{
memset(f,0,sizeof(f));
f[p[tot][1]]=1;
for (i=1;i<=k;++i)
{
for (j=p[tot][1];j>=0;--j)
{
f[j]=(f[j+1]+(ll)f[j]*inv[j+1])%M;
}
}
sum=0;
temp=1;
for (j=0;j<=p[tot][1];++j) //乘起来
{
sum=(sum+(ll)temp*f[j])%M;
temp=(ll)temp*p[tot][0]%M;
}
ans=(ll)ans*sum%M;
}
cout<<ans;
return 0;
}
int qpow(int x,int y) //快速幂，用于求逆元
{
int out=1;
while (y)
{
if (y&1)
{
out=(ll)out*x%M;
}
x=(ll)x*x%M;
y>>=1;
}
return out;
}
```