错排问题
白简
·
2021-07-21 10:19:39
·
个人记录
错排问题（Derangement）
概念释义
又叫错位排列、重排，即使一个排列所有的元素都不在原来的位置上。
错排问题是组合数学发展史上的一个重要问题，错排数也是一项重要的数。令 { a_k } ( 1 \leq k \leq n ) 是 n , n \epsilon N 的一个错排，如果每个元素都不在其对应下标的位置上，即 a_k \neq k ，那么这种排列称为错位排列，或错排、重排（Derangement）。
————————摘自《百度百科》简要分析
我们来看一个最为经典的错排问题，信封问题：共有 n 张信和 n 个信封，假设所有信都装错了信封，共有多少种情况？
我们先定义 f(n) 为当有 n 个信封和 n 张信时，有 f(n) 种错排方案。
当 n = 1 时，信只能放在它对应的信封中，不可能出现错排情况。
故 f(1) = 0 。
当 n = 2 时，只存在一种情况，即两张信交换位置。
故 f(2)=1 。
当 n = 3 时，存在着 3、1、2 和 2、3、1 两种情况，我们可以将其看为 1 与 2 错排，3 与 1、2 交换位置得来的。
故 f(3)=2 。
当 n = 4 时，错排有：
4 3 2 1，4 1 2 3，4 3 1 2，
//第一列是 4 分别与 123 互换位置，其余两个元素错排。
3 4 1 2，3 4 2 1，2 4 1 3，
//第二列是 4 分别与 312 （ 123 的一个错排）的每一个数互换
2 1 4 3，3 1 4 2，2 3 4 1。
//第三列则是由另一个错排 231 和 4 换位而得到
共 9 种情况。
根据上面的注释得知， f(n) 的值与 f(n-1) 、 f(n-2) 的值有一定的关联。
那我们能否得出递推式呢？答案是肯定的。
公式推导
首先，
### 然后，
假设 $1$ 号元素放在了第 $k$ 个位置，那么下一步就要排 $k$ 号元素。
### 再然后，
$k$ 号元素的排列有两种方式：
**一是放在第 $1$ 个位置**，剩下的 $n-2$ 个元素进行错排，共有 $f(n-2)$ 种可能；
**二是不放在第 $1$ 个位置**，这时我们将第 $1$ 个位置看作第 $k$ 个位置，于是就形成了包括 $k$ 号元素在内的 $n-1$ 个元素的错排，共有 $f(n-1)$ 种可能。
**所以，$k$ 号元素共有 $f(n-1)+f(n-2)$ 种可能。**
又因为第一号元素有 $n-1$ 种放法，根据乘法原理。
### 我们得知，
**递推式为：**
$f(n) =(n-1) \times (f(n-1)+f(n-2) )$。
以上就是基础错排问题的全部内容了（~~当然只是基础部分的全部内容~~）
## 练习题
### [P1595 信封问题](https://www.luogu.com.cn/problem/P1595)
这是一道模板题，只要你知道递推式便可以做对。此题也可以使用深度优先搜索来 AC 掉这道题。
不过需要注意的是，错排方案的增长非常快。
$n = 13$ 时 $int$ 会爆掉，$n = 22$ 时 $f(n)$ 的值就已经达到了约 $7\times 10^{18} $ , 在 $n = 23$ 时 $long$ $long$ 会爆掉。
也就是说，在处理错排问题时一定要开 $long$ $long$。
当题目给出 $n > 20$ 的范围时，我们就应该使用高精度算法了（~~Python、Java等略过~~）。
## Code
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
long long f(long long x)//一定要开long long
{
if( x == 1 )
return 0;
else if( x == 2 )
return 1;
else
return (x-1)*(f(x-1)+f(x-2));
}
int main()
{
int n;
cin>>n;
cout<<f(n);
return 0;
}
```
### [P3182 [HAOI2016]放棋子](https://www.luogu.com.cn/problem/P3182)
这道题也是一道裸错排题，不过数据到了 $200$ ，必定需要高精度。