神、上帝以及老天爷

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;
	}
}