problem

BOZJ3093

solution

逆概率公式，即貝葉斯(Bayes)公式：

假設 $B_1,B_2,...,B_n$ 是 $\Omega$ 的一個分割，$P(A)>0$，則有
$$P(B_k|A)=\frac{P(A{B}_k)}{P(A)}=\frac{P(B_k)P(A|B_k)}{{\sum }_{i=1}^{n}P(B_i)P(A|B_i)}$$
如果我們把事件 $A$ 看做結果，把諸事件 $B_1,B_2...$ 看做導致這個結果的可能的原因。

則可以形象地把全概率公式看做成為 由原因推結果。

而貝葉斯公式是 由結果推原因：現在有一個結果A 已經發(fā)生，在眾多可能的 原因 中，求這些 原因 導致了 結果A 的概率分別是多少，概率最大那個 原因 就最可能導致 結果A。
$$\sum _{m=0}^n{C}_{n?m}^i{C}_m^j=C_{n+1}^{i+j+1}$$

證明：

• 相當于有 $n+1$ 個球，編號從 $0～n$

  枚舉編號為 $m$ 的球必選，然后編號小于 $m$ 的球選 $j$ 個，編號大于 $m$ 的球選 $i$ 個

  一共就是從 $n+1$ 個中選 $i+j+1$ 個球的方案數

• 因為不管從哪個位置開始劃分，要求前后選的個數都是固定的

  一個數列中不可能有兩個位置滿足前后個數都一樣

  所以一定是不重的

---

對于本題，把選了 $p$ 個球其中有 $q$ 個是紅球看作結果 $A$，把原先一共有 $k$ 個紅球看作原因 $B_k$。

每一個原因的產生概率都是相同的，即 $P(B_k)=\frac{1}{n+1}$。

在某個原因下導致結果的概率，因為小球概率一樣可用組合數計算，即 $P(A|B_k)=\frac{C_k^q{C}_{n?k}^{p?q}}{C_n^p}$

先求某一種原因導致最后結果的概率：
$$P(B_k|A)=\frac{P(B_k)P(A|B_k)}{{\sum }_{i=0}^{n}P(B_i)P(A|B_i)}=\frac{\frac{1}{n+1}\frac{C_k^q{C}_{n?k}^{p?q}}{C_n^p}}{{\sum }_{i=0}^n\frac{1}{n+1}\frac{C_i^q{C}_{n?i}^{p?q}}{C_n^p}}=\frac{C_k^q{C}_{n?k}^{p?q}}{C_{n+1}^{p+1}}$$
最后的答案是求和每種原因導致結果后再抽一個紅球的概率。
$$ans=\sum _{k=0}^{n}P(B_k|A)?\frac{k?q}{n?p}=\sum _{k=0}^n\frac{C_k^q{C}_{n?k}^{p?q}}{C_{n+1}^{p+1}}?\frac{k?q}{n?p}=\frac{{\sum }_{k=0}^n{C}_k^q(k?q)C_{n?k}^{p?q}}{C_{n+1}^{p+1}(n?p)}$$

$$C_k^q(k?q)=\frac{k!}{q!(k?q!)}(k?q)=\frac{k!}{(k?q?1)!q!}=\frac{k!}{(k?q?1)!(q+1)!}(q+1)=C_k^{q+1}(q+1)$$

$$ans=\frac{{\sum }_{k=0}^n{C}_k^{q+1}(q+1)C_{n?k}^{p?q}}{C_{n+1}^{p+1}(n?p)}=\frac{(q+1)C_{n+1}^{p+2}}{(n?p)C_{n+1}^{p+1}}=\frac{(q+1)\frac{(n+1)!}{(p+2)!(n?p?1)!}}{(n?p)\frac{(n+1)!}{(p+1)!(n?p)!}}=\frac{q+1}{p+2}$$

code

因代碼過于簡單，所以就不放了

總結

以上是生活随笔為你收集整理的[BZOJ3093][Fdu校赛2012] A Famous Game（不等概率）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。