題目來源 ：http://acm.hdu.edu.cn/showproblem.php?pid=2048
神、上帝以及老天爺
Problem Description
HDU 2006'10 ACM contest的頒獎晚會隆重開始了！
為了活躍氣氛匣沼，組織者舉行了一個別開生面缆八、獎品豐厚的抽獎活動，這個活動的具體要求是這樣的：
首先，所有參加晚會的人員都將一張寫有自己名字的字條放入抽獎箱中湘捎；
然后尿招，待所有字條加入完畢矾柜，每人從箱中取一個字條；
最后就谜，如果取得的字條上寫的就是自己的名字怪蔑，那么“恭喜你，中獎了丧荐！”
大家可以想象一下當時的氣氛之熱烈缆瓣，畢竟中獎者的獎品是大家夢寐以求的Twins簽名照呀！不過虹统，正如所有試圖設計的喜劇往往以悲劇結(jié)尾弓坞，這次抽獎活動最后竟然沒有一個人中獎！
我的神窟却、上帝以及老天爺呀昼丑，怎么會這樣呢？
不過夸赫，先不要激動菩帝，現(xiàn)在問題來了，你能計算一下發(fā)生這種情況的概率嗎茬腿？
不會算呼奢？難道你也想以悲劇結(jié)尾？切平！
Input
輸入數(shù)據(jù)的第一行是一個整數(shù)C,表示測試實例的個數(shù)握础，然后是C 行數(shù)據(jù)，每行包含一個整數(shù)n(1
Output
對于每個測試實例悴品，請輸出發(fā)生這種情況的百分比禀综，每個實例的輸出占一行, 結(jié)果保留兩位小數(shù)(四舍五入)简烘，具體格式請參照sample output。
Sample Input
1
2
Sample Output
50.00%
思路：
一開始看到問題我就懵了定枷，這個好像是排列組合的問題好多情況啊覺得孤澎，自己想了好久沒有想到怎么做，被迫看了一下discuss欠窒，然后發(fā)現(xiàn)有個什么錯排公式覆旭；然后自己百度了一下錯排公式；具體可以看下它是這樣子說的
錯排問題
n個有序的元素應有n!個不同的排列岖妄，如若一個排列使得所有的元素不在原來的位置上型将，則稱這個排列為錯排；有的叫重排荐虐。
如七兜，1 2的錯排是唯一的，即2 1缚俏。1 2 3的錯排有31 2惊搏，2 3 1贮乳。這二者可以看作是1 2錯排忧换，3分別與1、2換位而得的向拆。
遞歸關(guān)系
為求其遞推關(guān)系亚茬，分兩步走：
第一步，考慮第n個元素浓恳，把它放在某一個位置刹缝，比如位置k，一共有n-1種放法颈将；
第二步梢夯，考慮第k個元素，這時有兩種情況：（1）把它放到位置n晴圾，那么對于除n以外的n-1個元素颂砸，由于第k個元素放到了位置n，所以剩下n-2個元素的錯排即可死姚，有
Dn-2種放法人乓；（2）第k個元素不放到位置n，這時對于這n-1個元素的錯排都毒，有Dn-1種放法色罚。
根據(jù)乘法和加法法則，綜上得到Dn=(n-1)(Dn-1+Dn-2)
特殊地账劲，D1=0,D2=1;
看不懂也沒有關(guān)系 這里有個很詳細的解釋?點我
現(xiàn)在有了錯排公式后戳护，這個題目就可以很簡單的解決了
這里有兩點是我學到的
1 對于這些遞歸解決的問題構(gòu)造遞歸函數(shù)會占好多內(nèi)存空間金抡；可以改成數(shù)組賦值這樣會快很多；
2 對于斐波那契數(shù)列遞歸到后面數(shù)值會很大腌且；所以要把數(shù)組定義為 long long
代碼如下：
# include <stdio.h>
long long JC (int i);
int main ()
{
int n=0,i=1;
long long a[25]={0,0,1};
for (i=3;i<=20;i++)
a[i]=(i-1)*(a[i-1]+a[i-2]);
scanf ("%d",&n);
while (n--)
{
scanf ("%d",&i);
printf ("%.2lf%%\n",(double)a[i]/JC(i)*100);
}
return 0;
}
long long JC (int i)
{
long long sum=1;
for (int j=2;j<=i;j++)
sum*=j;
return sum;
}
