洛谷 P1595：信封问题 ← 错排列

【题目来源】https://www.luogu.com.cn/problem/P1595【题目描述】某人写了 n 封信和 n 个信封如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。【输入格式】一个信封数 n保证 n≤20。【输出格式】一个整数代表有多少种情况。​​​​​​​【输入样例】3【输出样例】2【数据范围】对于 100% 的数据1≤n≤20。​​​​​​​【算法分析】● 错排Derangement问题是组合数学中的基本概念指 n 个元素中的每个元素都不在其对应下标的位置上即 ak≠k。其中k∈[1,n]。​​​​​​​例如1 2 3 4的错排有: 4 3 2 14 1 2 34 3 1 23 4 1 23 4 2 12 4 1 32 1 4 33 1 4 22 3 4 1。● 错排列公式D(n)(n-1)×(D(n-1)D(n-2))其中D(1)0D(2)1。第一步考虑第 n 个元素把它放在某一个位置比如位置 k一共有 n-1 种放法第二步考虑第 k 个元素这时有两种情况1把它放到位置 n那么对于除 n 以外的 n-1 个元素由于第 k 个元素放到了位置 n所以剩下 n-2 个元素的错排即可有 D(n-2) 种放法2第 k 个元素不放到位置 n这时对于这 n-1 个元素的错排有 D(n-1) 种放法。 根据乘法和加法法则综上可得D(n)(n-1)×(D(n-1)D(n-2))。● ​​​​​​​错排列公式D(n)nD(n-1)(-1)^n其中D(1)0。【算法代码】#include bits/stdc.h using namespace std; long long d(int n) { if(n1) return 0; if(n2) return 1; return (n-1)*(d(n-1)d(n-2)); } int main() { int n; cinn; coutd(n); return 0; } /* in:3 out:2 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/156206151https://www.luogu.com.cn/problem/solution/P1595