codeforces1097D Makoto and a Blackboard 数学+期望dp

题目传送门

题目大意：

　　给出一个n和k，每次操作可以把n等概率的变成自己的某一个因数，（6可以变成1,2,3,6，并且概率相等），问经过k次操作后，期望是多少？

思路：数学和期望dp 好题好题！！

　　直接考虑n到因子很难做，所以要研究从n到因子的一些性质。

　　如果一个数可以写成，p^c这样的形式，并且p是质数，那么如果把这个数进行上述的操作，他可以变成的形式必然是p^x（0<=x<=c），并且每个数的概率是平均的。

　　所以对于这样的数，我们可以得出dp方程，i表示第几次操作，j表示p^j。

　　dp[ i + 1 ][ j ] = dp[ i ][ x ] / ( j + 1 );( j <= x );

　　但是不是每个数都能写成p^c的形式的，但是每个数都能写成 p1^c1 * p2 ^c2 ……*pn ^ cn 的形式，所以我们就把一个数拆开，对每一个部分单独算期望，最后相乘，就是原来的期望了。

　　好题好题！！

#include<bits/stdc++.h>

const int inf=0x3f3f3f3f;

using namespace std;

typedef long long ll;

const ll p=1e9+;

const int maxn=;

ll inv[maxn];

ll dp[][];

ll c[maxn],m[maxn];

int len;

ll n,k;

void getinv() {

    inv[]=;

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

        inv[i]=(p-p/i)*inv[p%i]%p;

    }

}

int main() {

    cin>>n>>k;

    getinv();

    ll temp=n;

    for(ll i=; i*i<=temp; i++) {

        if(temp%i==) {

            c[++len]=i;

            while(temp%i==) {

                temp/=i;

                m[len]++;

            }

        }

    }

    if(temp!=)

        c[++len]=temp,m[len]=;

    ll ans=;

    for(int tep=; tep<=len; tep++) {

        memset(dp,,sizeof(dp));

        dp[][m[tep]]=;

        for(int i=; i<=k; i++) {

            for(int j=; j<=m[tep]; j++) {

                for(int t=j; t<=m[tep]; t++) {

                    dp[i][j] = (dp[i][j]+dp[i-][t]*inv[t+]%p)%p;

                }

            }

        }

        ll tmp=;

        ll di=;

        for(int j=; j<=m[tep]; j++) {

            tmp+=di*dp[k][j]%p;

            tmp%=p;

            di*=c[tep];

            di%=p;

        }

        ans=(ans*tmp)%p;

    }

    cout<<ans<<endl;

}

巴特西

codeforces1097D Makoto and a Blackboard 数学+期望dp

最新文章

热门文章