Bzoj3093 [Fdu校赛2012] A Famous Game

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 251 Solved: 136

Description

Mr. B and Mr. M like to play with balls. They have many balls colored in blue and red. Firstly, Mr. B randomly picks up N balls out of them and put them into a bag. Mr. M knows that there are N+1 possible situations in which the number of red balls is ranged from 0 to N, and we assume the possibilities of the N+1 situations are the same. But Mr. M does not know which situation occurs. Secondly, Mr. M picks up P balls out of the bag and examines them. There are Q red balls and P-Q blue balls. The question is: if he picks up one more ball out of the bag, what is the possibility that this ball is red?

袋子里有N个球，其中红球的个数可能为0~N，且每种情况概率相等。

现在从袋子里拿出P个球，发现其中Q个是红球，P-Q个是蓝球。

不放回球，如果再从袋子里拿出一个球，问拿出的是红球的概率是多少？

Input

Each test case contains only one line with three integers N, P and Q (2 <= N <= 100,000, 0 <= P <= N-1, 0 <= Q <= P).

Output

For each test case, display a single line containing the case number and the possibility of the next ball Mr. M picks out is red. The number should be rounded to four decimal places.

Sample Input

3 0 0
4 2 1

Sample Output

Case 1: 0.5000
Case 2: 0.5000

HINT

[Explanation]

For example as the sample test one, there are three balls in the bag. The possibilities of the four possible situations are all 0.25. If there are no red balls in the bag, the possibility of the next ball are red is 0. If there is one red ball in the bag, the possibility is 1/3. If there are two red balls, the possibility is 2/3. Finally if all balls are red, the possibility is 1. So the answer is 0*(1/4)+(1/3)*(1/4)+(2/3)*(1/4)+1*(1/4)=0.5.

Source

数学问题概率

推出来答案就是(q+1)/(p+2)

可能是近一年写过最短的代码

————————至于怎么推出来的？

http://www.cnblogs.com/neighthorn/p/6440645.html 参考了这里

首先要了解一些公式：

$ P(B)=sum P(Ai)*P(B|Ai) $ 全概率公式，A是前置条件，B发生的概率是A取遍所有情况下发生B的概率的和

$ P(A|B)=P(AB)/P(B) $ 条件概率公式，B条件下发生A的概率等于“同时发生AB的概率/发生B的概率”

然后看具体题目：

设事件A为：按照题意，再抽出一个球为红色球的概率

设事件B为：抽出P个球，其中有q个球为红色的概率

设事件Ki为：起初有Ki个红球的概率

$ ANS=P(A|B)/P(B)=frac{P(AB)}{P(B)} $

变形为

$frac{ sum_{i=0}^{N} P(AB|Ki)P(Ki)}{ sum_{i=0}^{N} P(B|Ki)P(Ki)}$

$frac{ sum_{i=0}^{N} P(A|BKi)*P(B|Ki)*P(Ki)}{ sum_{i=0}^{N} P(B|Ki)P(Ki)}$

上下形式很像，可惜K不同，不满足分配率，不能全约分掉

红球的个数从0~N等概率，所以每种情况出现的概率都是$ P(Ki)= frac{1}{n+1} $

所以上式的P(Ki)可以约掉了

剩下的部分怎么办？

$ P(B|Ki)=frac{C_{k}^{q}*C_{p-q}^{n-k} }{C_{n}^{p}} $

↑ 从红球中选q个的方案乘从蓝球中拿p-q个的方案除以所有拿的方案，看上去没毛病

$ P(A|BKi)=frac{P(ABKi)}{P(BKi)}=frac{k-q}{n-p} $

剩下n-p个球中有k-q个红球，看上去没毛病。也可以用条件概率公式约一波

得到：

$ frac{ sum_{i=0}^{N} frac{k-q}{n-p} *frac{ C_{k}^{q}C_{n-k}^{p-q}}{ C_{n}^{p}} } { sum_{i=0}^{N} frac{ C_{k}^{q}C_{n-k}^{p-q}}{ C_{n}^{p}}} $

那个$(k-q)/(n-p)$好麻烦，得想个办法处理掉。

$ C_{k}^{q}=frac{k!}{q!(k-q)!}=frac{k!}{q!(k-q-1)!}*(k-q) $

$ C_{k}^{q+1}=frac{k!}{(q+1)!(k-q-1)!}=frac{k!}{q!(k-q-1)!}*(q+1) $

于是把式子变形成：

$ frac{ sum_{i=0}^{N} frac{q+1}{n-p} *frac{ C_{k}^{q}C_{n-k}^{p-q}}{ C_{n}^{p}} } { sum_{i=0}^{N} frac{ C_{k}^{q}C_{n-k}^{p-q}}{ C_{n}^{p}}} $

这样就消除了又一处k的影响

从网上找来一个公式：

于是得到

$frac{C_{n+1}^{p+2}}{C_{n+1}^{p+1}} *frac{q+1}{n-p}$

再一化简就是(q+1)/(p+2)

————————

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=100010;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10-'0'+ch;ch=getchar();}
    return x*f;
}
int n,p,q;
int main(){
    int cas=0;
    while(scanf("%d%d%d",&n,&p,&q)!=EOF){
        printf("Case %d: %.4f
",++cas,(q+1.0)/(p+2.0));
    }
    return 0;
}