uva557

摘要:概率推公式

正文:
Description
Download as PDF
When Mr. and Mrs. Clinton’s twin sons Ben and Bill had their tenth birthday, the party was held at the McDonald’s restaurant at South Broadway 202, New York. There were 20 kids at the party, including Ben and Bill. Ronald McDonald had made 10 hamburgers and 10 cheeseburgers and when he served the kids he started with the girl directly sitting left of Bill. Ben was sitting to the right of Bill. Ronald flipped a (fair) coin to decide if the girl should have a hamburger or a cheeseburger, head for hamburger, tail for cheeseburger. He repeated this procedure with all the other 17 kids before serving Ben and Bill last. Though, when coming to Ben he didn’t have to flip the coin anymore because there were no cheeseburgers left, only 2 hamburgers.

Ronald McDonald was quite surprised this happened, so he would like to know what the probability is of this kind of events. Calculate the probability that Ben and Bill will get the same type of burger using the procedure described above. Ronald McDonald always grills the same number of hamburgers and cheeseburgers.
Input
The first line of the input-file contains the number of problems n , followed by n times:

a line with an even number [2,4,6,…,100000], which indicates the number of guests present at the party including Ben and Bill.
Output
The output consists of n lines with on each line the probability (4 decimals precise) that Ben and Bill get the same type of burger.

Note: a variance of $\pm 0.0001$ is allowed in the output due to rounding differences.
Sample Input

3
6
10
256

Sample Output

0.6250
0.7266
0.9500

有n个汉堡,n为偶数,一半是香辣的,一半是…无所谓,反正不一样的品种,然后n个煞笔小孩拿汉堡,如果两种都有,那么拿的概率是1/2,如果只剩下一种,那么就是100%拿剩下的那种汉堡,问最后两个煞笔拿到同一种汉堡的概率。

一开始的想法显然是直接艹公式,然后推出:
设m为n的一半
$(1/2)^{m}C_{m}^{m} + (1/2)^{m + 1}C_{m + 1}^{m} + (1/2)^{m + 2}C_{m + 2}^{m} + …$

但是这个做法很蛋疼,因为n能到10000,然后每次pow,精度直接就没有了…

然后从反面考虑(正难则反,强行考虑),算出不一样的概率。
那就是一直到最后两个汉堡一定是2种汉堡。表达式就是
$(1/2)^{n - 2}C_{n - 2}^{m - 1}$
这个表达式显然是可以递推的,那就直接预处理,O(1)查询。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<utility>
#include<sstream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
double f[50010];
int main()
{

#ifdef LOCAL
freopen("C:\\Users\\ΡΡ\\Desktop\\in.txt","r",stdin);
//freopen("C:\\Users\\ΡΡ\\Desktop\\out.txt","w",stdout);
#endif // LOCAL
int t;
scanf("%d",&t);
f[1] = 1;
for(int i = 2;i <= 50000;i++)
f[i] = f[i - 1]*(2*i - 3)/(2*i - 2);
while(t--){
int n;
scanf("%d",&n);
if(n == 2){
printf("0.0000\n");
continue;
}
printf("%.4lf\n",1 - f[n/2]);
}
return 0;
}