uva 11762 数学期望+记忆化搜索

题目大意：给一个正整数N，每次可以在不超过N的素数中随机选择一个P，如果P是N的约数，则把N变成N/p,否则N不变，问平均情况下需要多少次随机选择，才能把N变成1？

分析：根据数学期望的线性和全期望公式可以为每个状态列出一个方程，例如： f(x)=1+f(6)*1/3+f(3)*1/3+f(2)*1/3

等式右边的最前面的“1”是指第一次转移，而后面的几项是后续的转移，用全期望公式展开，一般地，设不超过x的素数有p个，其中有g个是x的因子，则

f(x)=1+f(x)*(1-g/p)+Σf(x/y)/p

边界f(1)=0。移项后整理得

f(x)=(Σf(x/y)+p)/g

因为x/y<x，可以用记忆化搜索的方式计算f(x)。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std; 

const int Max=;

int prime[],Num;

bool flag[Max],vis[Max];

double f[Max];

void Init()

{

    int i,j;

    Num=;

    for(i=;i<Max;i++)

    {

        if(flag[i]) prime[Num++]=i;

        for(j=;j<Num && i*prime[j]<Max;j++)

        {

            flag[i*prime[j]]=false;

            if(i%prime[j]==) break;

        }

    }

}

double dp(int x)

{

    if(x==) return 0.0;

    if(vis[x]) return f[x];

    vis[x]=true;

    double sum=;

    int p=,g=;

    for(int i=;i<Num && prime[i]<=x;i++)

    {

        p++;

        if(x%prime[i]==)

        {

            g++;

            sum+=dp(x/prime[i]);

        }

    }

    sum=(sum+p)/g;

    return f[x]=sum;

}

int main()

{

    memset(flag,true,sizeof(flag));

    memset(vis,false,sizeof(vis));

    memset(f,0.0,sizeof(f));

    Init();

    int t,i,n;

    scanf("%d",&t);

    for(i=;i<=t;i++)

    {

        scanf("%d",&n);

        printf("Case %d: %.10lf\n",i,dp(n));

    }

    return ;

}

巴特西

uva 11762 数学期望+记忆化搜索

最新文章

热门文章