[BZOJ3093][Fdu校赛2012] A Famous Game(不等概率)

problem

BOZJ3093

solution

逆概率公式,即贝叶斯(Bayes)公式:

假设 B 1 , B 2 , . . . , B n B_1,B_2,...,B_n B1​,B2​,...,Bn​ 是 Ω \Omega Ω 的一个分割, P ( A ) > 0 P(A)>0 P(A)>0,则有
P ( B k ∣ A ) = P ( A B k ) P ( A ) = P ( B k ) P ( A ∣ B k ) ∑ i = 1 n P ( B i ) P ( A ∣ B i ) 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​)​
如果我们把事件 A A A 看做结果,把诸事件 B 1 , B 2 . . . B_1,B_2... B1​,B2​... 看做导致这个结果的可能的原因

则可以形象地把全概率公式看做成为 由原因推结果

而贝叶斯公式是 由结果推原因:现在有一个结果A 已经发生,在众多可能的 原因 中,求这些 原因 导致了 结果A 的概率分别是多少,概率最大那个 原因 就最可能导致 结果A
∑ m = 0 n C n − m i C m j = C n + 1 i + 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 + 1 n+1 n+1 个球,编号从 0 ∼ n 0\sim n 0∼n

    枚举编号为 m m m 的球必选,然后编号小于 m m m 的球选 j j j 个,编号大于 m m m 的球选 i i i 个

    一共就是从 n + 1 n+1 n+1 个中选 i + j + 1 i+j+1 i+j+1 个球的方案数

  • 因为不管从哪个位置开始划分,要求前后选的个数都是固定的

    一个数列中不可能有两个位置满足前后个数都一样

    所以一定是不重的


对于本题,把选了 p p p 个球其中有 q q q 个是红球看作结果 A A A,把原先一共有 k k k 个红球看作原因 B k B_k Bk​。

每一个原因的产生概率都是相同的,即 P ( B k ) = 1 n + 1 P(B_k)=\frac{1}{n+1} P(Bk​)=n+11​。

在某个原因下导致结果的概率,因为小球概率一样可用组合数计算,即 P ( A ∣ B k ) = C k q C n − k p − q C n p P(A|B_k)=\frac{C_k^qC_{n-k}^{p-q}}{C_n^p} P(A∣Bk​)=Cnp​Ckq​Cn−kp−q​​

先求某一种原因导致最后结果的概率:
P ( B k ∣ A ) = P ( B k ) P ( A ∣ B k ) ∑ i = 0 n P ( B i ) P ( A ∣ B i ) = 1 n + 1 C k q C n − k p − q C n p ∑ i = 0 n 1 n + 1 C i q C n − i p − q C n p = C k q C n − k p − q C n + 1 p + 1 P(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​​
最后的答案是求和每种原因导致结果后再抽一个红球的概率。
a n s = ∑ k = 0 n P ( B k ∣ A ) ⋅ k − q n − p = ∑ k = 0 n C k q C n − k p − q C n + 1 p + 1 ⋅ k − q n − p = ∑ k = 0 n C k q ( k − q ) C n − k p − q C n + 1 p + 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​​

C k q ( k − q ) = k ! q ! ( k − q ! ) ( k − q ) = k ! ( k − q − 1 ) ! q ! = k ! ( k − q − 1 ) ! ( q + 1 ) ! ( q + 1 ) = C k q + 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)

a n s = ∑ k = 0 n C k q + 1 ( q + 1 ) C n − k p − q C n + 1 p + 1 ( n − p ) = ( q + 1 ) C n + 1 p + 2 ( n − p ) C n + 1 p + 1 = ( q + 1 ) ( n + 1 ) ! ( p + 2 ) ! ( n − p − 1 ) ! ( n − p ) ( n + 1 ) ! ( p + 1 ) ! ( n − p ) ! = q + 1 p + 2 ans=\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

因代码过于简单,所以就不放了

上一篇:mysql


下一篇:部署 Kubernetes 持久化存储 GlusterFS