錯排問題（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\) 號元素必定要排在第 \(2\sim n\) 個位置的其中之一，所以有 \(n-1\) 種放法，
然后，
假設 \(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 信封問題
這是一道模板題，只要你知道遞推式便可以做對，此題也可以使用深度優先搜索來 AC 掉這道題，
不過需要注意的是，錯排方案的增長非常快，
\(n = 13\) 時 \(int\) 會爆掉，\(n = 22\) 時 \(f(n)\) 的值就已經達到了約 \(7\times 10^{18}\) , 在 \(n = 23\) 時 \(long\) \(long\) 會爆掉，
也就是說，在處理錯排問題時一定要開 \(long\) \(long\)，
當題目給出 \(n > 20\) 的范圍時，我們就應該使用高精度演算法了（Python、Java等略過），
Code
#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]放棋子
這道題也是一道裸錯排題，不過資料到了 \(200\) ，必定需要高精度，
具體代碼筆者不再展示，留作讀者思考，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/500572.html
標籤：C++