MatRush@ZJUT

其实HDU2048就是这题的弱化版，这题只是把错排巧妙的加进去了。

考虑n对夫妇，从中挑出m位，再进行错排，那题目就可以解决了。错排在上一篇日志有讲了，而n选m则是典型的组合数学，由于这是递推求解专题练习，所以我们采用递推的方式来计算组合数和错排数。
递推公式如下：

f[n][m] = c[n][m] * d[m];
c[n][m] = c[n-1][m] + c[n-1][m-1];//组合数C(n,m)
d[m] = (m-1)*(d[m-1]+d[m-2]);//错排数D[m]

其实计算错排数在n比较小的时候(大约小于13)使用近似公式

D(n)=[n!/e+0.5]

([x]是高斯函数，表示不超过x的最大整数)会比较好，况且这题是离线的题，我们也完全可以自己计算20以内的错排数来打表。不过这些就不是题目的本意了。

代码如下：

/*
ID:Shuaicpp
Prog:HDU2049-不容易系列之(4)——考新郎
Lang:C++
Algorithm:DP-f[n][m] = c[n][m] * d[m];
             c[n][m] = c[n-1][m] + c[n-1][m-1];
             d[m] = (m-1)*(d[m-1]+d[m-2]);
*/
#include <iostream>
using namespace std;
const int MAXN = 21;
long long c[MAXN][MAXN],d[MAXN];
int main()
{
    int n,m,k;
    d[1] = 0;
    d[2] = 1;
    for (int i = 3;i < MAXN;i++)
        d[i] = (i-1)*(d[i-1]+d[i-2]);
    for (int i = 0;i < MAXN;i++)
    {
        c[i][0] = 1;
        c[i][1] = i;
    }
    for (int i = 2;i < MAXN;i++)
        for (int j = 2;j <= i;j++)
            c[i][j] = c[i-1][j-1] + c[i-1][j];
    cin >> k;
    for (int i = 0;i < k;i++)
    {
        cin >> n >> m;
        cout << c[n][m] * d[m] << endl;
    }
    return 0;
}

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

第一次的dp思路：

用f[i][j]表示第i位为j色的满足要求的涂法，分三次进行取方案数,则递推方程如下：

f[i][0] = f[i-1][1] + f[i-1][2];(color[1] != 0)
f[i][1] = f[i-1][0] + f[i-1][2];(color[1] != 1)
f[i][2] = f[i-1][0] + f[i-1][1];(color[1] != 2)

则

ans = (f[n][1] + f[n][2]) + (f[n][0]+f[n][2]) + (f[n][0]+f[n][1]);

更简单的递推思路：
考虑长为n的串，以s[i]表示i位的字符。
1.若前n-1位组成的串合法，则由于首尾不同，再添加一位时，只有1种方法；即s[n] != s[n-1] != s[1]。
2.若前n-1位组成的串不合法，再添加一位后合法，即因为首尾相同而引起的不合法，那么前n-2位组成的串必定合法。此时第n位有2种添加方法。即s[n] != s[n-1] = s[1]。
3.边界条件：f(1)=3;f(2)=6;f(3)=6。

/*
ID:Shuaicpp
Prog:HDU2045-不容易系列之(3)—— LELE的RPG难题
Lang:C++
Algorithm:DP-f[i]=f[i-1]+f[i-2]*2(i>3);边界f[1] = 3,f[2] = 6,f[3] = 6;
*/
#include <iostream>
#include <cmath>
using namespace std;
const int n = 51;
long long f[n] = {0};
int main()
{
    f[1] = 3;
    f[2] = 6;
    f[3] = 6;
    for (int i = 4;i < n;i++)
        f[i] = f[i-1] + f[i-2] * 2;
    int x;
    while (cin >> x)
        cout << f[x] << endl;
    return 0;
}