题解 P1595 【信封问题】

题解在博客[食用](http://www.cnblogs.com/YoungNeal/p/8485399.html)效果更佳哦~ 我们先来科普一下错排问题，oier们以后也会用到/ 错排问题指考虑一个有 $n$ 个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 $n$ 个元素的错排数记为 $D(n)$ 。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。 ---《百度百科》 看上去这就是一个递推问题，那么递推式是如何推出来呢？ 当 $n$ 个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用 $D(n)$ 表示，那么 $D(n-1)$ 就表示 $n-1$ 个编号元素放在 $n-1$ 个编号位置，各不对应的方法数，其它类推. 第一步，把第 $n$ 个元素放在一个位置，比如位置 $k$ ，一共有 $n-1$ 种方法； 第二步，放编号为 $k$ 的元素，这时有两种情况：⑴把它放到位置 $n$ ，那么，对于剩下的 $n-1$ 个元素，由于第 $k$ 个元素放到了位置 $n$ ，剩下 $n-2$ 个元素就有 $D(n-2)$ 种方法；⑵第 $k$ 个元素不把它放到位置 $n$ ，这时，对于这 $n-1$ 个元素，有 $D(n-1)$ 种方法； 综上得到 $D(n) = (n-1) *(D(n-2) + D(n-1))$ 特殊地，$D(1) = 0, D(2) = 1$. 这就是错排问题。理解了这个，还可以去做一道省选的错排[裸题](https://www.luogu.org/problemnew/show/P3182). 上代码 ``` #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; int f[25],n; int main() { scanf("%d",&n); f[1]=0;f[2]=1;f[3]=2; if(n==1||n==2||n==3) { printf("%d",f[n]); return 0; } for(int i=4;i<=n;i++) { f[i]=(i-1)*(f[i-1]+f[i-2]); } printf("%d",f[n]); return 0; } ```