[期待dp+记忆化搜索] light oj 1038 Race to 1 Again

[期望dp+记忆化搜索] light oj 1038 Race to 1 Again

题意：

给一个数n，每次随机选它的一个约数去除n，直到除到1为止，问除的次数的期望。

思路：

E[n]= E[n/a[1]]/cnt+E[n/a[2]]/cnt+...+E[n/a[n]]/cnt+1

a[i]为n的约数，cnt为约数的个数。

显然a[i]=1  则(1-1/cnt)E[n]=E[n/a[2]]/cnt+...+E[n/a[n]]/cnt+1

记忆化搜索就ok了~

代码：

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#include"map"
#include"stack"
#include"vector"
#define ll __int64
#define eps 1e-8
#define inf -999999999999999999LL
using namespace std;
double dp[123567];
double dfs(int x)
{
    if(x==1) return 0.0;
    if(fabs(dp[x]+1)>eps) return dp[x];
    int cnt=0;
    double ans=1.0;
    int lit=sqrt(x*1.0);
    for(int i=1; i<=lit; i++)   //统计因子数
    {
        if(x%i==0)
        {
            if(i*i==x) cnt++;
            else cnt+=2;
        }
    }
    for(int i=1; i<=lit; i++)  //求期望的和
    {
        if(x%i==0)
        {
            if(i*i==x) ans+=1.0/cnt*dfs(x/i);
            else
            {
                if(i!=1) ans+=1.0/cnt*dfs(x/i);
                ans+=1.0/cnt*dfs(i);
            }
        }
    }
    ans=ans/(1-1.0/cnt);
    return dp[x]=ans;
}
int main()
{
    int t,cas=1;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("Case %d: %.7f\n",cas++,dfs(n));
    }
    return 0;
}