题目链接：传送门
题意：n个盒子里装有礼物，m个人随机选择礼物，选完之后空盒子放回。问选中的礼物数的期望。
题解：
解法一：一个礼物m次不被选中的概率是 <nobr> (n−1n)m </nobr>，那么不被选的期望就是 <nobr> n×(n−1n)m </nobr>,所以用总数减去不被选的期望就是被选中礼物的期望
解法二：也可以用概率求期望，用 <nobr> f[i] </nobr>表示第 <nobr> i </nobr>个人得到礼物的概率，那么如果第 <nobr> i−1 </nobr>个人没有得到礼物，那么第 <nobr> i </nobr>个人和第 <nobr> i−1 </nobr>个人得到礼物的概率一样；反之，则第 <nobr> i </nobr>个人得到礼物的概率应该是第 <nobr> i−1 </nobr>个人得到礼物的概率减去 <nobr> 1n </nobr>，由此可以得到递推式
<nobr> f[i]=(1−f[i−1])×f[i−1]+f[i−1]×(f[i−1]−1n) </nobr>
这道题的思路比较特殊
代码一：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> 
using namespace std;

int n,m;
double p,ans;

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        p=1.0*(n-1)/n;
        ans=n-n*pow(p,m);
        printf("%.10lf\n",ans);
    }
}

代码二：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> 
using namespace std;

const int N=100010;
int n,m;
double f[N],ans;

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        f[1]=1,ans=1;
        for(int i=2;i<=m;i++)
            f[i]=(1.0-f[i-1])*f[i-1]+f[i-1]*(f[i-1]-1.0/n),ans+=f[i];
        printf("%.10lf\n",ans); 
    }
    return 0;
}