[BZOJ3093][Fdu校赛2012] A Famous Game(不等概率)
problem
BOZJ3093
solution
逆概率公式,即貝葉斯(Bayes)公式:
假設 B1,B2,...,BnB_1,B_2,...,B_nB1?,B2?,...,Bn? 是 Ω\OmegaΩ 的一個分割,P(A)>0P(A)>0P(A)>0,則有
P(Bk∣A)=P(ABk)P(A)=P(Bk)P(A∣Bk)∑i=1nP(Bi)P(A∣Bi)P(B_k|A)=\frac{P(AB_k)}{P(A)}=\frac{P(B_k)P(A|B_k)}{\sum_{i=1}^nP(B_i)P(A|B_i)} P(Bk?∣A)=P(A)P(ABk?)?=∑i=1n?P(Bi?)P(A∣Bi?)P(Bk?)P(A∣Bk?)?
如果我們把事件 AAA 看做結果,把諸事件 B1,B2...B_1,B_2...B1?,B2?... 看做導致這個結果的可能的原因。
則可以形象地把全概率公式看做成為 由原因推結果。
而貝葉斯公式是 由結果推原因:現在有一個結果A 已經發(fā)生,在眾多可能的 原因 中,求這些 原因 導致了 結果A 的概率分別是多少,概率最大那個 原因 就最可能導致 結果A。
∑m=0nCn?miCmj=Cn+1i+j+1\sum_{m=0}^nC_{n-m}^iC_{m}^j=C_{n+1}^{i+j+1} m=0∑n?Cn?mi?Cmj?=Cn+1i+j+1?
證明:
-
相當于有 n+1n+1n+1 個球,編號從 0~n0\sim n0~n
枚舉編號為 mmm 的球必選,然后編號小于 mmm 的球選 jjj 個,編號大于 mmm 的球選 iii 個
一共就是從 n+1n+1n+1 個中選 i+j+1i+j+1i+j+1 個球的方案數
-
因為不管從哪個位置開始劃分,要求前后選的個數都是固定的
一個數列中不可能有兩個位置滿足前后個數都一樣
所以一定是不重的
對于本題,把選了 ppp 個球其中有 qqq 個是紅球看作結果 AAA,把原先一共有 kkk 個紅球看作原因 BkB_kBk?。
每一個原因的產生概率都是相同的,即 P(Bk)=1n+1P(B_k)=\frac{1}{n+1}P(Bk?)=n+11?。
在某個原因下導致結果的概率,因為小球概率一樣可用組合數計算,即 P(A∣Bk)=CkqCn?kp?qCnpP(A|B_k)=\frac{C_k^qC_{n-k}^{p-q}}{C_n^p}P(A∣Bk?)=Cnp?Ckq?Cn?kp?q??
先求某一種原因導致最后結果的概率:
P(Bk∣A)=P(Bk)P(A∣Bk)∑i=0nP(Bi)P(A∣Bi)=1n+1CkqCn?kp?qCnp∑i=0n1n+1CiqCn?ip?qCnp=CkqCn?kp?qCn+1p+1P(B_k|A)=\frac{P(B_k)P(A|B_k)}{\sum_{i=0}^nP(B_i)P(A|B_i)}=\frac{\frac{1}{n+1}\frac{C_k^qC_{n-k}^{p-q}}{C_n^p}}{\sum_{i=0}^n\frac{1}{n+1}\frac{C_i^qC_{n-i}^{p-q}}{C_n^p}}=\frac{C_k^qC_{n-k}^{p-q}}{C_{n+1}^{p+1}} P(Bk?∣A)=∑i=0n?P(Bi?)P(A∣Bi?)P(Bk?)P(A∣Bk?)?=∑i=0n?n+11?Cnp?Ciq?Cn?ip?q??n+11?Cnp?Ckq?Cn?kp?q???=Cn+1p+1?Ckq?Cn?kp?q??
最后的答案是求和每種原因導致結果后再抽一個紅球的概率。
ans=∑k=0nP(Bk∣A)?k?qn?p=∑k=0nCkqCn?kp?qCn+1p+1?k?qn?p=∑k=0nCkq(k?q)Cn?kp?qCn+1p+1(n?p)ans=\sum_{k=0}^nP(B_k|A)·\frac{k-q}{n-p}=\sum_{k=0}^n\frac{C_k^qC_{n-k}^{p-q}}{C_{n+1}^{p+1}}·\frac{k-q}{n-p}=\frac{\sum_{k=0}^nC_{k}^{q}(k-q)C_{n-k}^{p-q}}{C_{n+1}^{p+1}(n-p)} ans=k=0∑n?P(Bk?∣A)?n?pk?q?=k=0∑n?Cn+1p+1?Ckq?Cn?kp?q???n?pk?q?=Cn+1p+1?(n?p)∑k=0n?Ckq?(k?q)Cn?kp?q??
Ckq(k?q)=k!q!(k?q!)(k?q)=k!(k?q?1)!q!=k!(k?q?1)!(q+1)!(q+1)=Ckq+1(q+1)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) Ckq?(k?q)=q!(k?q!)k!?(k?q)=(k?q?1)!q!k!?=(k?q?1)!(q+1)!k!?(q+1)=Ckq+1?(q+1)
ans=∑k=0nCkq+1(q+1)Cn?kp?qCn+1p+1(n?p)=(q+1)Cn+1p+2(n?p)Cn+1p+1=(q+1)(n+1)!(p+2)!(n?p?1)!(n?p)(n+1)!(p+1)!(n?p)!=q+1p+2ans=\frac{\sum_{k=0}^nC_{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} ans=Cn+1p+1?(n?p)∑k=0n?Ckq+1?(q+1)Cn?kp?q??=(n?p)Cn+1p+1?(q+1)Cn+1p+2??=(n?p)(p+1)!(n?p)!(n+1)!?(q+1)(p+2)!(n?p?1)!(n+1)!??=p+2q+1?
code
因代碼過于簡單,所以就不放了
總結
以上是生活随笔為你收集整理的[BZOJ3093][Fdu校赛2012] A Famous Game(不等概率)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: [NOIP2021] 数列(计数dp)
- 下一篇: 安卓微店店长版不提示声音(安卓微店)