UVa 557 - Burger

Published on 2016-03-09

题目地址

描述

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

样例输入

3
6
10
256

样例输出

0.6250
0.7266
0.9500

分析

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

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

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

即:

f[n]=n3n2f[n2]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;
}

附加输入

10
546
12
2
236
694
43256
23554
14414
69450
10000

附加输出

0.9658
0.7539
0.0000
0.9479
0.9697
0.9962
0.9948
0.9934
0.9970
0.9920