题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=495
题目大意：有N个盒子，里面都放着礼物，M个人依次去选择盒子，每人仅能选一次，如果里面有礼物则将礼物取出来，把空盒子放回原位，若没有礼物，则把空盒子放回原位。求礼物被拿走的个数的数学期望。
令 x[i] 代表第i个人拿到的礼物的个数，即值为0或1。
那么，N个人拿到的礼物的个数为 X = Sigma(X[i])。
因此 E[X] = E[Sigma(X[i])] = Sigma(E[X[i]])
其中，X[i]服从两点分布，即E[X[i]] = P(i)。
定义状态f[i]代表第i个人能够抓到礼物的概率，可以将样本空间划分为第i-1个人拿到了礼物和第i-1个人没拿到礼物。
因此有 P(i) = P(i|~i-1) + P(i|i-1) 即 f[i] = f[i-1]*(f[i-1]-1/n)+(1-f[i-1])*f[i-1]
化简得f[i] = f[i-1]*(1-1/n)。
进一步。。数学期望就可以用等比数列求和公式来做了。。。。。
有代码：
///#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <cmath>
#include <numeric>
#include <iterator>
#include <iostream>
#include <cstdlib>
#include <functional>
#include <queue>
#include <stack>
#include <string>
#include <cctype>
using namespace std;
#define PB push_back
#define MP make_pair
#define SZ size()
#define ST begin()
#define ED end()
#define CLR clear()
#define ZERO(x) memset((x),0,sizeof(x))
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const double EPS = 1e-; const int MAX_N = +; double f[MAX_N];
int N,M; int main() {
while( ~scanf("%d%d",&N,&M) ) {
f[] = 1.0;
double ans = 1.0;
for( int i=;i<=M;i++ ){
f[i] = (1.0-f[i-])*f[i-] + f[i-]*( f[i-]-1.0/N );
ans += f[i];
}
printf("%.11f\n",ans);
}
return ;
}