2016 多校联赛7 Balls and Boxes(概率期望)

时间:2021-05-08 07:30:18
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==?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-);
if(a==)
printf("0/1\n");
else
{
b=m*m;
long long g=gcd(a,b);
printf("%lld/%lld\n",a/g,b/g);
}
}
return ;
}