递推——错排

错排问题

n个有序的元素应有n!个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排。
问题举例：写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己。

递推公式

当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.

第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；
第二步，放编号为k的元素，这时有两种情况：

1. 把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法
2. 第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；

综上得到
D(n) = (n-1) [D(n-2) + D(n-1)]，特殊地，D(1) = 0，D(2) = 1。
n很大时，简化后的公式是D(n) = [n!/e+0.5] ，其中e是自然对数的底，[x]为x的整数部分。

错排公式的应用

例1：
题目描述：参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；之后每人从箱中取一个字条；如果取得的字条上写的就是自己的名字，那么中奖了。这次抽奖活动最后没有一个人中奖，计算一下发生这种情况的概率。
Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(1<n<=20),表示参加抽奖的人数。
Output
对于每个测试实例，请输出发生这种情况的百分比，每个实例的输出占一行, 结果保留两位小数(四舍五入)，具体格式请参照sample output。
Sample Input
1
2

Sample Output
50.00%

解：直接用错排公式求出，再除n！即为概率

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
ll jc(int i) {
  ll sum = 1;
    for (int j = 2; j <= i; j++)
        sum *= j;
    return sum;
}
int main () {
    int n = 0, num;
    ll a[25] = {0, 0, 1};
    for (int i = 3; i <= 20; i++)
        a[i] = (i-1) * (a[i-1]+a[i-2]);
    cin >> n;
    while (n--) {
        cin >> num;
        printf ("%.2lf%%\n",(double)a[num]/jc(num)*100);
    }
}

例2：
题目描述：假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1<M<=N<=20)。

Output
对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。

Sample Input
2
2 2
3 2

Sample Output
1
3

解：N对新婚夫妇，M对找错，其实就是现在N里面选出M，C(N,M)=n!/(n-m)!*m! ，然后考虑M对夫妇错排的情况

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
int main () {
    int n, m, c;
    ll a[25] = {0, 0, 1};
    for (int i = 3; i <= 20; i++)
        a[i] = (i-1) * (a[i-1]+a[i-2]);
    ll sum1, sum2;
    cin >> c;
    while (c--) {
      sum1 = sum2 = 1;
    cin >> n >> m;
      for (int i = n; i > n-m; i--)
        sum1 *= i;
      for (int i = 2; i <= m; i++)
        sum2 *= i;
    cout << sum1/sum2*a[m] <<endl;  
  }    
}