神、上帝以及老天爷

Problem Description
HDU 2006’10 ACM contest的颁奖晚会隆重开始了!
为了活跃气氛,组织者举行了一个别开生面、奖品丰厚的抽奖活动,这个活动的具体要求是这样的:

首先,所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中;
然后,待所有字条加入完毕,每人从箱中取一个字条;
最后,如果取得的字条上写的就是自己的名字,那么“恭喜你,中奖了!”

大家可以想象一下当时的气氛之热烈,毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀!不过,正如所有试图设计的喜剧往往以悲剧结尾,这次抽奖活动最后竟然没有一个人中奖!

我的神、上帝以及老天爷呀,怎么会这样呢?

不过,先不要激动,现在问题来了,你能计算一下发生这种情况的概率吗?

不会算?难道你也想以悲剧结尾?!

Input
输入数据的第一行是一个整数C,表示测试实例的个数,然后是C 行数据,每行包含一个整数n(1<n<=20),表示参加抽奖的人数。

Output
对于每个测试实例,请输出发生这种情况的百分比,每个实例的输出占一行, 结果保留两位小数(四舍五入),具体格式请参照sample output。

Sample Input
1
2

Sample Output
50.00%
解题思路:

  1. 先清楚题目,题目要求的是没有一个人中奖的概率(因为我就看错了题目qwq)
  2. 没有一个人中奖的概率=每个人不中奖的概率/全部概率
  3. 全部概率:n的全排列,即n!
  4. 每个人不中奖的概率:每个人拿到纸条都不是自己写的。我们把这个概率求出来就可以了,这里用到的是错位排序公式:D(N)=(N-1)*[(D(N-1))+D(N-2)],其中D(1)=0,D(2)=1.
  5. 即解题公式:没有一个人中奖的概率=D(N)=(N-1)*[(D(N-1))+D(N-2)]/N!。

公式的证明是用容斥原理证明的,学艺不精,无法给出证明,只能解释一下:
//在这里d(n)表示错位序列的个数。

  1. 什么是错位排序:即与原来位置全部不相同的一组序列,例如n=3时,1 2 3 是一组序列,他的位错序列是 2 3 1和3 1 2。

  2. 好,现在来考虑n的错位序列的个数。假设,n-1已经是一个排好了的错位序列,这个时候n不是错位的,但是我可以和前面任意n-1个交换位置,就能让整个序列变得是错位序列,即公式d(n)=(n-1)*d(n-1)。(其中n-1代表d(n-1)这个序列)

  3. 还有一个情况:假设前面n-1个人不满足错排序列,但是这个时候n和其中的一个交换就能够变得是错排,即n-2是满足错排的,n-1不是错排,这个自己在本子上笔画一下就知道了,(这个时候有n-1一种一个不是错排,其他都是错排的情况),即有公式(n-1)*d(n-2)(d(n-2)代表n-2已经是错排和n交换能够得到所有错排的情况)
    这里稍微列举了几组数据:

  4. 将两式相加就得到我们想要的公式了:d(n)=(n-1)*(d(n-1)+d(n-2)),有了这个公式,程序很快就能写出来了,至于公式的证明等我研究得差不多在一起讨论一下。

一下是ac代码(c++):

#include<iostream>
#include<iomanip>
#define max 1000
using namespace std;
double res[max];//求错排的总数
int main()
{
	res[1]=0;
	res[2]=1;
	int n,a;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		long long int sum=1;
		cin>>a;
		for(int k=1;k<=a;k++)
		{
			sum*=k;//求阶乘
		}
		//cout<<sum<<endl;
		if(a==2)
		{
			cout<<"50.00%"<<endl;
			continue;
		}
		for(int j=3;j<=a;j++)
		{
			res[j]=(j-1) * (res[j-1]+res[j-2]);
		}
		cout<<fixed<<setprecision(2)<<(res[a]/sum)*100<<"%"<<endl;
	}
}