题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5810

题意:

将$n$个球随机放入$m$个盒子中，求$V={ {\sum_{i=1}^m(X_i-\bar{X})^2}\over m}$的期望。

分析：

推导一：

可以将问题看成样本数量（实验次数）为m的，将n个球放入m个盒子中，观察某一盒子中的球个数的实验。
由$E[V] = E[{ {\sum_{i=1}^m(X_i-\bar{X})^2}\over m}]=E[(X_i-\bar{X})^2]=E[X_i^2-2X_i\bar{X}+{\bar{X}^2}]=E[X_i^2]-\bar{X}^2$
已知$D(X)=E(X^2)-[E(X)]^2$，因此有$E[V]=D[X_i]$
对于某个样本来说，即一次实验，为$n$次伯努利实验， 方差为$n\times{1\over m}\times{(m-1) \over m}$。

推导二：

$V = \sum_{i=1}^m {X_i^2\over m}-2\bar{X}{n\over m}+\bar{X}^2= \sum_{i=1}^m {X_i^2\over m}-{n^2\over m^2}=E[X_i^2]-{n^2\over m^2}$
关键是要求$E[X_i^2]$
用随机变量$Y_j$表示第$j$个球是否在第$i$个盒子中，在$Y_j=1$，否则$Y_j=0$
那么有
$E[X_i^2]=E[(\sum_{j=1}^nY_j)^2]=E[\sum_{j=1}^n Y_j^2]+2E[\sum_{j=1}^n\sum_{k=1,k!=j}^nY_jY_k]
=nE[Y_j^2]+(n-1)nE[Y_jY_k]=\frac{n}{m}+\frac{n(n-1)}{m^2}$
所以$E[V] = \frac{n}{m} + \frac{n(n-1)}{m^2} - \frac{n^2}{m^2} = \frac{n(m-1)}{m^2}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/*************************************************************************
    > File Name: 7.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/9 14:02:54
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b)
{
	return b?gcd(b, a % b):a;
}
int main (void)
{
	ll n, m;
	while(scanf("%lld%lld", &n, &m) && (n + m)){
		if(m == 1){
			puts("0/1");
			continue;
		}
		ll a = n * (m - 1);
		ll b = m * m;
		ll g = gcd(a, b);
		printf("%lld/%lld\n", a / g, b / g);
	}
	return 0;
}