UVa 557 - Burger | Sengxian's Blog

UVa 557 - Burger

#数学 #概率

Published on 2016-03-09

描述

一共有 $n(2\le n\le {10}^5, n \bmod 2 = 0)$ 个人，厨师准备了 $\frac{n}{2}$ 个汉堡和 $\frac{n}{2}$ 个芝士堡，它会顺着上餐，用硬币决定上菜类型，有 $\frac{1}{2}$ 的概率上汉堡，有 $\frac{1}{2}$ 的概率上芝士堡，问有多大的概率，使得最后两个人得到的相同的汉堡。

样例输入

样例输出

0.6250
0.7266
0.9500

分析

首先明确我们所求的概率 $P$ 等于所有符合条件的序列数量除以所有序列数量。
观察到如果要求符合条件的序列的话，要讨论，比较麻烦，考虑求不符合条件的序列。如果一个序列不符合条件，那么在剩余最后两个人的时候，一定剩余 1 个芝士堡和 1 个汉堡，那么之前发的 $n - 2$ 个堡中，发了 $\frac{n}{2} - 1$ 个汉堡。
设 $f[n]$ 为有 $n$ 个人，不符合条件的概率，则答案为 $1 - f[n]$ ，容易求得：

f[n] = \frac{C_{n - 2}^{\frac{n}{2} - 1}}{2 ^ {n - 2}}

注意到这个式子在 $n$ 很大的时候不好求，常见的手段是考虑使用对数，但组合数求的话复杂度是 $O(n)$ 的，总的复杂度高达 $O(n^2)$ ，TLE！
只能搞一搞递推：首先有 $f[2] = 1$ （注意是不符合条件的概率）

即：

f[n] = \frac{n-3}{n-2}f[n - 2]

代码

//  Created by Sengxian on 3/9/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 542 Probablity
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <numeric>
#include <vector>
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 1) + (n << 3) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100000 + 3;
double f[maxn];

int main() {
    f[2] = 1;
    for(int i = 4; i < maxn; i += 2) f[i] = f[i - 2] * (double)(i - 3) / (i - 2); 
    int caseNum = ReadInt();
    while(caseNum--) printf("%.4lf\n", 1 - f[ReadInt()]);
    return 0;
}

附加输入

附加输出

造 BestCoder Round #75 之记 UVa 10090 - Marbles