Codeforces 1097D. Makoto and a Blackboard

首先考虑如果 $n$ 只有一个质因数的情况，即 $n=p^t$

那么显然可以 $dp$ ，设 $f[i][j]$ 表示第 $i$ 步，当前剩下 $p^j$ 的概率

那么转移很简单： $f[i][j]=\sum_{k=j}^{t}\frac{f[i-1][k]}{k+1}$ ，然后可以发现 $f[i][j+1]$ 算的在 $f[i][j]$ 里面都会算到，那么可以把转移优化一下：

$f[i][j]=f[i][j+1]+\frac{f[i-1][j]}{j+1}$ ，然后复杂度就很稳

现在考虑一下 $n=\prod_{i=1}^{m} p_{i} ^ {t_i}$ 的情况，发现直接把每个质数的贡献分别算然后乘起来即可

可以这样考虑，首先概率显然是可以乘起来的，然后发现当两件事情同时发生：剩下 $p_{x} ^ {a}$ 和剩下 $p_{y} ^ {b}$

贡献即为$p_{x} ^ {a} p_{y} ^ {b} $ ，发现刚好也是相乘的，所以直接相乘即可

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=,M=1e4+,mo=1e9+;

inline int fk(int x) { return x>=mo ? x-mo : x; }

ll n,m;

int p[N],cnt[N],inv[N],tot;

int f[M][N],Ans=;

int main()

{

    n=read(),m=read();

    int T=sqrt(n); ll now=n;

    for(int i=;i<=T;i++)

    {

        if(now%i) continue;

        p[++tot]=i; while(now%i==) cnt[tot]++,now/=i;

    }

    if(now>) p[++tot]=now%mo,cnt[tot]=;

    inv[]=;

    for(int i=;i<N;i++)

        inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;

    for(int i=;i<=tot;i++)

    {

        memset(f,,sizeof(f)); f[][cnt[i]]=;

        for(int j=;j<=m;j++)

        {

            f[j][cnt[i]]=1ll*f[j-][cnt[i]]*inv[cnt[i]+]%mo;

            for(int k=cnt[i]-;k>=;k--)

                f[j][k]=fk(f[j][k+]+1ll*f[j-][k]*inv[k+]%mo);

        }

        int pw=,res=;

        for(int j=;j<=cnt[i];j++)

        {

            res=fk(res+1ll*f[m][j]*pw%mo);

            pw=1ll*pw*p[i]%mo;

        }

        Ans=1ll*Ans*res%mo;

    }

    printf("%d\n",Ans);

    return ;

}

巴特西

Codeforces 1097D. Makoto and a Blackboard

最新文章

热门文章