2016 多校联赛7 Balls and Boxes（概率期望）

Mr. Chopsticks is interested in random phenomena, and he conducts an experiment to study randomness. In the experiment, he throws n balls into m boxes in such a manner that each ball has equal probability of going to each boxes. After the experiment, he calculated the statistical variance V as 

V=∑mi=1(Xi−X¯)2mV=∑i=1m(Xi−X¯)2m

where XiXi is the number of balls in the ith box, and X¯X¯ is the average number of balls in a box. 
Your task is to find out the expected value of V. 

InputThe input contains multiple test cases. Each case contains two integers n and m (1 <= n, m <= 1000 000 000) in a line. 
The input is terminated by n = m = 0. 
OutputFor each case, output the result as A/B in a line, where A/B should be an irreducible fraction. Let B=1 if the result is an integer.Sample Input

2 1
2 2
0 0

Sample Output

0/1
1/2


        
 

Hint

In the second sample, there are four possible outcomes, two outcomes with V = 0 and two outcomes with V = 1.

概率期望问题，启发博客：http://blog.csdn.net/xzxxzx401/article/details/52167534 以下

• 首先这是一个二项分布。对于一个盒子来说，n次实验是扔n个球，每次进入盒子概率是1/m。样本方差的期望等于总体的方差！证明爱看不看。直接的结果：E(V)=n∗(m−1)m2

• 有不用这个性质直接推出公式的。膜大神。

  E(V)=E(∑ni=0(Xi−X¯)2)m=E(x2)−2∗nm∗E(x)+n2m2 
  E(x)=nm 
  E(x2)=D(x)+[Ex]2 
  二项分布，D(x)=n∗(m−1)m2 
  所以带到上面的式子中就变成了E(V)=n∗(m−1)m2

• 官方题解我是看不懂。

  E[V]=E[∑mi=1(Xi−X¯)2m]=E[(Xi−X¯)2]=E[X2i−2XiX¯+X¯2] 
  =E[X2i]−2X¯E[Xi]+E[X¯2]=E[X2i]−2X¯2+X¯2=E[X2i]−n2m2 
  所以关键是要求出E[X2i]. 我们用随机变量Yj来表示第j个球是否在第i个盒子中，如果在则Yj=1，否则Yj=0. 于是 
  E[X2i]=E[(∑nj=1Yj)2]=E[∑nj=1Y2j]+2E[∑nj=1∑nk=1,k≠jYjYk]=nE[Y2j]+n(n−1)E[YjYk] 
  =nm+n(n−1)m2 
  因此， 
  E[V]=nm+n(n−1)m2−n2m2=n(m−1)m2

#include<iostream>
#include<cstdio>
using namespace std;

long long gcd(long long b,long long c)//计算最大公约数
{
return c==0?b:gcd(c,b%c);
}

int main()
{
    long long n,m;
    long long a,b;
    while(~scanf("%lld%lld",&n,&m)&&(n+m))
    {
        a=n*(m-1);
        if(a==0)
            printf("0/1
");
        else
        {
            b=m*m;
            long long g=gcd(a,b);
            printf("%lld/%lld
",a/g,b/g);
        }
    }
    return 0;
}