UVa 11762 (期望 DP) Race to 1

时间：2024-09-20 17:08:02

设f(x)表示x转移到1需要的次数的期望，p(x)为不超过x的素数的个数，其中能整除x的有g(x)个

则有(1-g(x)/p(x))的概率下一步还是转移到x，剩下的情况各有1/p(x)的概率转移到x/y

根据全期望公式，f(x) = 1 + (1-g(x)/p(x)) * f(x) + sum{ 1/p(x) * f(x/y) | y是能整除x且不超过x的素数 }

代码是用记忆化搜索计算f的

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 using namespace std;

 const int maxn = ;

 bool vis[maxn + ];

 int prime[], pcnt = ;

 void prime_table()

 {

     int m = sqrt(maxn + 0.5);

     for(int i = ; i <= m; i++) if(!vis[i])

         for(int j = i*i; j <= maxn; j += i) vis[j] = true;

     for(int i = ; i <= maxn; i++) if(!vis[i]) prime[pcnt++] = i;

 }

 double d[maxn + ];

 double dp(int x)

 {

     if(x == ) return ;

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

     vis[x] = ;

     double& ans = d[x];

     int p = , g = ;

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

     {

         p++;

         if(x % prime[i] == ) { ans += dp(x / prime[i]); g++; }

     }

     ans = (ans + p) / g;

     return ans;

 }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     prime_table();

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

     int T;

     scanf("%d", &T);

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

     {

         int x;

         scanf("%d", &x);

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

     }

     return ;

 }

代码君

相关文章