我是来搞笑的

这题就是让你求一个长度为

k

的排列的错排数。

错排就是第

i

个数字不是

i

的排列。

翻了一下题解和网络，发现只有我一个傻逼试图用容斥推导错排公式。

结果推出来的式子和题解都不一样（噗）

那就做一次傻逼吧。设一下错排数列，推导的思路就是容斥的基本思路：

\text{设}\,f\left( n \right) \text{表示长度为}n\text{的错排}

直接按照思路写下公式

f\left( n \right) =\sum_{i=0}^n{\left( -1 \right) ^i\left( \begin{array}{c} n \\ i \end{array} \right) \left( n-i \right) !}

看见后面是

(n-i)!

，回想一下组合数公式就会发现我们可以把组合数拆了:

=\sum_{i=0}^n{\left( -1 \right) ^i\frac{n!}{i!}}

提出来

=n!\left( \sum_{i=0}^n{\left( -1 \right) ^i\frac{1}{i!}} \right)

尝试递推，我们列出

f(n-1)

的式子看看要加几项才可以变成

f(n)

f\left( n-1 \right) =\left( n-1 \right) !\left( \sum_{i=0}^{n-1}{\left( -1 \right) ^i\frac{1}{i!}} \right)

把

(n-1)!

乘个

n

变成

n!

之后, 括号里面只缺多出来的

(-1)^n \frac{1}{n!}

这一项，把括号拆了, 乘进去发现是

n\times f\left( n-1 \right) =\sum_{i=0}^{n-1}{\left( -1 \right) ^i\frac{n!}{i!}}

那么补上剩下的

(-1)^n \frac{n!}{n!}

就可以得到

f\left( n \right) =n \times f\left( n-1 \right) +\left( -1 \right) ^n

然后这么递推是

\mathcal{O}(n)

的。

我还生成了一个图

讨论操作