题目链接：https://vjudge.net/problem/SGU-495
题意：n个奖品 m个人， 每个人会拿一个盒子， 盒子里面可能是空的 因为里面的奖品可以被其他人拿过，盒子每次放回，奖品会拿走

问m个人能拿到的奖品数的期望

思路：dp[0]=0 这是边界   那么考虑 dpi] 为前i个人能拿的奖品期望数  所以转移方程dp[i]=dp[i-1] (上一次拿的奖品期望)+ (n-dp[i-1])/n  这一次拿的奖品期望

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define pb push_back
 5 const int maxn =1e6+10;
 6 const int mod=1e9+7;
 7 
 8 double dp[maxn];
 9 
10 
11 int main()
12 {
13     ios::sync_with_stdio(false);
14     cin.tie(0);
15     int n,m;
16     cin>>n>>m;
17     dp[0]=0;
18     for(int i=1;i<=m;i++)
19     {
20         dp[i]=dp[i-1]+(n-dp[i-1])/(double)n;
21     }
22     cout<<fixed<<setprecision(10)<<dp[m]<<'\n';
23 
24 
25 
26 
27 
28 }

View Code