SGU 495

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long 
 4 const ll inf  = 1000000000000;
 5 const int N  =100010;
 6 int n,m;
 7 double dp[N];
 8 /*
 9 有N个礼物，M次选择，每次取的可能是未被选到的礼物
10 (礼物取走把空盒子放回可以被别人再次选择)
11 也有可能是空盒子，问你M次选择后被选走的礼物数目的期望
12 */
13 int main()
14 {
15     /*
16     dp[i] :第i个人选择后共取走礼物数目的期望
17     显然dp[1]= 1.0(只能选出一个，并且一定会被选到（因为没有空盒子）)
18     dp[i]之前别人共选走的礼物数目的期望+这次第i个人选到礼物的期望
19     dp[i] = dp[i-1]+(n-dp[i-1])/n
20     */
21     scanf("%d%d",&n,&m);
22     dp[1]= 1.0;
23     for(int i =2;i<=m;i++){
24         dp[i] =dp[i-1]+(n*1.0-dp[i-1])/n;
25     }
26     printf("%.10f
",dp[m]);
27     return 0;
28 }