ouuan 的博客

ouuan 的博客

题解 CF1097D 【Makoto and a Blackboard】

posted on 2019-01-06 13:29:19 | under 题解 |

这里是复杂度为 $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)$ (质因数个数)。

#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;
}