神、上帝以及老天爷
Problem Description
HDU 2006’10 ACM contest的颁奖晚会隆重开始了!
为了活跃气氛, 组织者举行了一个别开生面、奖品丰厚的抽奖活动, 这个活动的具体要求是这样的：
首先, 所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中;
然后, 待所有字条加入完毕, 每人从箱中取一个字条;
最后, 如果取得的字条上写的就是自己的名字, 那么“恭喜你, 中奖了! ”
大家可以想象一下当时的气氛之热烈, 毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀! 不过, 正如所有试图设计的喜剧往往以悲剧结尾, 这次抽奖活动最后竟然没有一个人中奖!
我的神、上帝以及老天爷呀, 怎么会这样呢?
不过, 先不要激动, 现在问题来了, 你能计算一下发生这种情况的概率吗?
不会算? 难道你也想以悲剧结尾?!
Input
输入数据的第一行是一个整数C, 表示测试实例的个数, 然后是C 行数据, 每行包含一个整数n(1 < n <= 20), 表示参加抽奖的人数。
Output
对于每个测试实例, 请输出发生这种情况的百分比, 每个实例的输出占一行, 结果保留两位小数(四舍五入), 具体格式请参照sample output。
Sample Input
1 | 1 |
Sample Output
1 | 50.00% |
Source
Analyze
这是一道组合数学的问题: 记参加抽奖的人数为n, 则此时无人中奖的概率为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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
下面我们讨论```a[n]```, 我们采用递推的思想, 有两种情况:
(1) 已知抽奖人数为n-1时所有人都不中奖的情况为```a[n-1]```, 此时将这n-1个人中的某个人与第n个人交换字条, 这时候得到```(n-1) * a[n-1]```种n个人都不中奖的情况;
(2) 已知抽奖人数为n-1时只有一个人中奖的情况为```b[n-1]```, 此时将这个中奖的人与第n个人交换字条, 这时候得到```b[n-1]```种n个人都不中奖的情况。
因此当抽奖人数为n时有```a[n] = (n-1) * a[n-1] + b[n-1]```成立
这时候讨论```b[n]```为抽奖人数为n时只有一个人中奖的情况:
(1) 第n个人中奖, 前n-1个人都没有中奖则有```a[n-1]```种情况;
(2) 前n-1个人中有一个人中奖, 而第n个人不中奖, 从前n-1个人中选取某一个人(记为x)与持有字条x的人交换字条, 并将x原有的字条给第n个人, 而第n个人的字条给原持有字条x的人, 此时有```(n - 1) * a[n-1]```种情况。
## Code
```C++
#include <bits/stdc++.h>
#define fei(a, b) for(int i = a; i <= b; i++)
#define fej(a, b) for(int j = a; j <= b; j++)
#define fni(a, b) for(int i = a; i < b; i++)
#define fnj(a, b) for(int j = a; j < b; j++)
using namespace std;
const int maxn = 20 + 5;
long long a[maxn];
long long b[maxn];
long long c[maxn];
int main()
{
// freopen("in.txt", "r", stdin);
int x;
cin >> x;
a[2] = 1;
b[2] = 0;
fei(3, 20)
{
a[i] = a[i - 1] * (i - 1) + b[i - 1];
b[i] = i * a[i - 1];
}
c[0] = 1;
fei(1, 20)
c[i] = c[i - 1] * i;
while(x--)
{
int n;
cin >> n;
double ans = 1.0 * a[n] / c[n] * 100;
printf("%.2lf", ans);
cout << "%" << endl;
}
return 0;
}
