概率DP light oj 1038

t个数据

然后一个n

输出变成1的期望

看个数据

dp[n]代表n变成1的期望

cnt代表因子个数 pi代表因子

那么dp[n]=1/cnt*(dp[n/p1]+1)+1/cnt*(dp[n/p2]+1)...

为什么加1呢就是走到这个数要加一步

整理可得dp[n]=1/(cnt-1)(dp[n/p1]+dp[n/p2]...+cnt);

 1 #include <stdio.h>
 2 #include<algorithm>
 3 #include<math.h>
 4 
 5 using namespace std;
 6 
 7 #define MAXN 100010
 8 
 9 double dp[MAXN];
10 
11 int main()
12 {
13     int t,ca;
14     scanf("%d",&t);
15     ca=1;
16     dp[1]=0;
17 
18     for(int i=2;i<=100000;i++)
19     {
20         double en=sqrt(1.0*i);
21         int cnt=0;
22         dp[i]=0;
23 
24         for(__int64 j=1;j<=en;j++)
25         {
26             if(i%j==0)
27             {
28                 if(i/j==j)  //去一下同样的
29                 {
30                     cnt++;
31                     dp[i]+=dp[j];
32                 }
33                 else
34                 {
35                     cnt+=2;
36                     dp[i]+=dp[i/j];
37                     dp[i]+=dp[j];
38                 }
39             }
40         }
41         dp[i]=(dp[i]+cnt)/(cnt-1);
42     }
43 
44     while (t--)
45     {
46         int n;
47         scanf("%d",&n);
48         printf("Case %d: %.6lf
",ca++,dp[n]);
49     }
50 
51     return 0;
52 }