概率 light oj 1248

t组样例

n<100010

dp[i] 从i翻到n面的期望

接下来翻可能是i面已经有的也可能是n-i面没有的

dp[i]=i/n*(dp[i]+1)+(n-i)/n*(dp[i+1]+1);

dp[n]=0;

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 #include<math.h>
 5 
 6 using namespace std;
 7 
 8 #define MAXN 100010
 9 double dp[MAXN];
10 
11 int main()
12 {
13     int t,ca;
14     ca=1;
15     scanf("%d",&t);
16     while(t--)
17     {
18         int n;
19         scanf("%d",&n);
20         dp[n]=0;
21         for(int i=n-1;i>=0;i--)
22         {
23             dp[i]=dp[i+1]+double(n)/(n-i);
24         }
25         printf("Case %d: %.6lf
",ca++,dp[0]);
26     }
27 
28 
29     return 0;
30 }