1.容斥。
设$f[i]$为至少有$i$个不合法的位置的方案数，至少->奇减偶加，得到答案。
对于$f[i]$，$f[i]=C_n^i \times (n-i)!$
关于容斥，打算单写一篇。
2.含义。
递推式$f_i=(i-1)\times(f_{i-2}+f_{j-1})$
设当前我考虑到第$i$个数，那么这个数只有除位置$i$外的$(n-1)$种选择。
设i放到了位置k上，对k这个数的放位置分类
a.放到位置$i$上，那么$i$和$k$的位置都确定了，方案数为剩下的错排$f_{n-2}$。
b.没放位置$i$上，此时可以理解为$k$不能放到位置$n$，相当于n-1个数的错排$f_{n-1}$。
原文：https://www.cnblogs.com/hzoi-yzh/p/11644618.html