hdu4554 A Famous Game 概率期望

题面

题意：n个球，2种颜色，可能有0~n个红球,每种情况的概率相同。现在从箱子里取出了$p$个球，其中有$Q$个是红球,问现在再取一个球是红球的概率为多少？

题解：因为0 ~ n的概率相同，所以每个球是红色的概率不互相独立。设A表示下一个球是红色这个事件，B表示取了$p$个球，有$Q$个红球这个事件，$N_{k}$表示一开始袋子里有$k$个红球。那么我们就是要求$P(A | B)$
$$P(A|B) = frac{P(AB)}{P(B)} = frac{sum_{k = 0}^{n} P(AB | N_{k}) P(N_{k})}{sum_{k = 0}^{n}P(B | N_{k}) P(N_{k})}$$
$$= frac{sum_{k = 0}^{n} P(A | BN_{k}) P(B | N_{k}) P(N_{k})}{sum_{k = 0}^{n} P(B | N_{k})}$$
分析可知：$$P(A | BN_{k}) = frac{k - Q}{N - p}, P(N_{k}) = frac{1}{N + 1}, P(B | N_{k}) = frac{C_{k}^{Q} C_{N - k}^{p - Q}}{C_{N}^{p}}$$
代入原式：
$$frac{sum_{k = 0}^{N} frac{k - Q}{N - p} frac{C_{k}^{Q} C_{N - k}^{p - Q}}{C_{N}^{p}} frac{1}{N + 1}}{sum_{k = 0}^{N} frac{C_{k}^{Q} C_{N - k}^{p - Q}}{C_{N}^{p}}frac{1}{N + 1}}$$
$$=frac{sum_{k = 0}^{N} frac{k - Q}{N - p} frac{C_{k}^{Q} C_{N - k}^{p - Q}}{C_{N}^{p}} }{sum_{k = 0}^{N} frac{C_{k}^{Q} C_{N - k}^{p - Q}}{C_{N}^{p}}}$$
$$=frac{sum_{k = 0}^{N} (k - Q) frac{C_{k}^{Q} C_{N - k}^{p - Q}}{C_{N}^{p}} }{sum_{k = 0}^{N} (N - p) frac{C_{k}^{Q} C_{N - k}^{p - Q}}{C_{N}^{p}}}$$
先尝试对分子进行化简：
$$frac{k!}{Q!(k - Q)!} frac{(N - k)!}{(p - Q)! (N - k - p + Q)!}(k - Q)$$
观察到第一个分式的分母可以和$(k - Q)$约掉得到$frac{k!}{Q!(k - Q - 1)!}$.
如果能把这个式子也变成组合数的形式，会更有利于化简，观察到$(k - Q - 1)!$其实对应的是$C_{k}^{Q + 1}$,因此我们尝试把这个部分表示为$C_{k}^{Q + 1}$,那么下面就要多乘一个$Q + 1$,相当于给整个式子除了一个$Q + 1$,因此我们在末尾再把$Q + 1$乘回来，于是得到原式为：
$$frac{sum_{k = 0}^{N} C_{k}^{Q + 1} C_{N - k}^{p - Q} (Q + 1)}{sum_{k = 0}^{N} C_{k}^{Q} C_{N - k}^{p - Q}(N - p)}$$
$$frac{sum_{k = 0}^{N} C_{k}^{Q + 1} C_{N - k}^{p - Q}}{sum_{k = 0}^{N} C_{k}^{Q} C_{N - k}^{p - Q}} frac{Q + 1}{N - p}$$
因为有$$sum_{k = 0}^{s} C_{k}^{n} C_{s - k}^{m} = C_{s + 1}^{n + m + 1}$$

原因：可以看做是有$s + 1$个物品，要从里面取$n + m + 1$个，这个式子就相当于是在枚举第$n + 1$个取走了第$k + 1$。然后再在前$k$个中取$n$个，在后$s + 1 - k - 1 = s - k$中取$m$个。

所以对原式化简得到:$frac{Q + 1}{p + 2}$

#include<bits/stdc++.h>
using namespace std;
#define R register int 

void work()
{
    double n, p, q; int tot = 0;
    while(scanf("%lf%lf%lf", &n, &p, &q) != EOF) 
        printf("Case %d: %.4lf
", ++ tot, (q + 1) / (p + 2));
}

int main()
{
    freopen("in.in", "r", stdin);
    work();
    fclose(stdin);
    return 0;
}