SGU 495 Kids and Prizes

数学方法：

从每个箱子来考虑：m次选择以后，至少有一次被选中的概率为 $1-(frac{n-1}{n})^m$ .因为这些箱子是相互独立的，所以被选中的箱子数的期望为 $nleft [ 1-(frac{n-1}{n})^m ight ]$

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n, m;
 9     while(scanf("%d%d", &n, &m) == 2)
10     {
11         double ans = n * 1.0 * (1.0 - pow((1.0 - (1.0 / n)), m));
12         printf("%.12f
", ans);
13     }
14 
15     return 0;
16 }

代码君

DP：

也可以从人来考虑，设d(i)为第i个人中奖的概率，则

如果第i-1个人没有中奖，那么第i个人中奖和第i-1个人中奖的概率是一样的；

如果第i-1个人中奖，那么第i个人中奖的概率就要比第i-1个人中奖的概率少1/n.

所以d(i) = d(i-1) * (d(i-1) - 1/n) + (1 - d(i-1)) * d(i-1)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 const int maxn=110000;
 8 double dp[maxn];
 9 int main()
10 {
11     double n,m;
12     while (scanf("%lf %lf",&n,&m)==2)
13     {
14         double sum=1.0;
15         dp[1]=1;
16         for(int i=2;i<=m;i++)
17         {
18             dp[i]=(1-dp[i-1])*dp[i-1]+dp[i-1]*(dp[i-1]-1.0/n);
19             sum+=dp[i];
20         }
21         printf("%.9f
",sum);
22     }
23     return 0;
24 }

代码君