MatRush@ZJUT

N张字条的所有排列可能自然是A(N,N)= N!种排列方式
现在的问题就是N张字条的错排方式有几种。分两种情况讨论
①：如果前面N-1个人拿的都不是自己的字条，即前N-1个人满足错排，那么只要第N个人把自己的票与前面N-1个人中的任意一个交换，就可以满足N个人的错排。这时有f(N-1)种方法。

②：如果前N-1个人不满足错排，而第N个人把自己的字条与其中一个人交换后恰好满足错排。即在前面N-1人中，有N-2个人满足错排，有且只有一个人拿的是自己的字条，而第N个人恰好与他做了交换，这时候就满足了错排。这时有f(n-2)种方法

对于①，因为前N-1个人中，每个人都有机会与第N个人交换，所以有N-1种交换的可能。
对于②，因为前N-1个人中，每个人都有机会拿着自己的字条。所以也有N-1种交换的可能。

所以得错排递推公式

D[n] = (n-1)*(D[n-1]+D[n-2])

由于计算n!和D[n]数字会非常大，所以我们采用边做边除而不是先算D(n)，再除n!的方法。

已知D[n]=(n-1)(D[n-1]+D[n-2]);
令f[n]=D[n]/n!;则有D[n]=n!*f[n];
代入可得f[n]=(n-1)/n!*(f[n-1]*(n-1)!+f[n-2]*(n-2)!);
整理有f[n]=(n-1)/n*(f[n-1]+f[n-2]);
即得到错排概率公式f[n]=(n-1)/n*(f[n-1]+f[n-2]);

代码如下：

/*
ID:Shuaicpp
Prog:HDU2048-神、上帝以及老天爷
Lang:C++
Algorithm:DP-f[n] = ((n-1)*f[n-1]+f[n-2]) / n;
*/
#include <iostream>
#include <iomanip>
using namespace std;
const int MAXN = 20;
double f[MAXN];
int main()
{
    int n,x;
    f[1] = 0;
    f[2] = 0.5;
    for (int i = 3;i <= MAXN;i++)
        f[i] = ((i-1)*f[i-1]+f[i-2]) / i;
    cin >> n;
    for (int i = 0;i < n;i++)
    {
        cin >> x;
        cout << fixed << setprecision(2) << f[x] * 100 << '%' << endl;
    }
    return 0;
}