【HDU】5810 Balls and Boxes

31 Aug 2016

Balls and Boxes

题目链接

Balls and Boxes

题目大意

现在有n个球丢进m个箱子里，给出了一个V： \[ V=\frac{\sum_{i=1}^m(X_i-\bar X)^2}{m} \] 现在要求这个V的期望。

题解

期望计算

\[ E[V]=E[\frac{\sum_{i=1}^m(X_i-\bar X)^2}{m}] \] \[ \therefore E[V]=(X_i-\bar X)^2 \] \[ \therefore E[V]=({X_i}^2-2X_i\bar X+{\bar X}^2) \] \[ \therefore E[V]=E[{X_i}^2]-{\bar X}^2 \] \[ \therefore E[V]=D[X_i]+E[X_i]^2-{\bar X}^2 \] 最终得到 \[ E[V]=D[X_i] \] 又因为\(X_i\) 其实就是一个二项分布，最后直接套公式就行了，得到最终结果： \[ E[V]=\frac{n(m-1)}{m^2} \]

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long

using namespace std;

LL n,m;

LL gcd(LL a,LL b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}

int main()
{
    while (scanf("%I64d%I64d",&n,&m),n!=0 || m!=0)
    {
        LL a,b,c;
        if (m==1)
        {
            printf("0/1\n");
            continue;
        }
        a=(m-1)*n; b=m*m;
        c=gcd(a,b);
        a/=c; b/=c;
        printf("%I64d/%I64d\n",a,b);
    }
    return 0;
}