Uva11762 Race to 1——有向无环图&&记忆化搜索

题意

给出一个整数 $N$，每次可以在不超过 $N$ 的素数中等概率随机选择一个 $P$，如果 $P$ 是 $N$ 的约数，则把 $N$ 变成 $N/P$，否则 $N$ 不变。问平均情况下需要多少次随机选择，才能把 $N$ 变成1呢？

分析

本题可以画出一个状态转移图，

例如 $n=6$ 时，

$n$ 的每个约数都对应一个状态，每个状态转移都有一定概率，从每个状态出发转移的概率和为1.

设 $f(i)$ 表示当前的数为 $i$ 时接下来需要选择的期望次数，可列出方程：

$$f(6) = 1 + f(6)/3 + f(3)/3 + f(2)/3$$

一般地，设不超过 $x$ 的素数有 $p(x)$ 个，其中有 $g(x)$ 个是 $x$ 的因子，则

$$f(x) = 1 + f(x) \times [1 - \frac{g(x)}{p(x)}] + \sum_{x | y} \frac{f(x/y)}{p(x)}$$

即

$$f(x) = \frac{\sum _{x|y}f(x/y) + p(x)}{g(x)}$$

边界为 $f(1)=0$，因为 $x/y < x$（即形成的是有向无环图），可以用记忆化搜索的方式 计算 $f(x)$，否则就要用高斯消元了。

#include<bits/stdc++.h>

using  namespace std;

//返回n以内素数的个数

//埃氏筛法O(nloglogn)

const int maxn =  + ;

int prime[maxn];            //prime[i]表示第i个素数

bool is_prime[maxn + ];    //is_prime[i]为true表示i是素数

int prime_cnt;

int sieve(int n)

{

    int cnt = ;

    for (int i = ; i <= n; i++)  is_prime[i] = true;

    is_prime[] = is_prime[] = false;

    for (long long i = ; i <= n; i++)

    {

        if (is_prime[i])

        {

            prime[cnt++] = i;

            for (long long j = i * i; j <= n; j += i)  is_prime[j] = false;  //i * i可能爆int

        }

    }

    return cnt;

}

bool vis[maxn];

double f[maxn];

double dp(int x)

{

    //printf("x: %d\n", x);

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

    if(x == )  return 0.0;

    vis[x] = ;

    double& ans = f[x];

    int g = , p = ;    //累加g[x] 和 p[x]

    ans = ;

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

    {

        p++;

        if(x % prime[i] == )

        {

            g++;

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

        }

    }

    ans = (ans + p) / g;

    return ans;

}

int n;

int main()

{

    prime_cnt = sieve();

    int T, kase = ;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &n);

        printf("Case %d: %.8f\n", ++kase, dp(n));

    }

    return ;

}