错排是简单的。

排列组合是简单的。

但没关同步流。导致挂 $40$ 分。检查出他是困难的！！！！！

警示后人：十年OI一场空，没关同步流见祖宗！！！

---

关于错排

递推式： $f_i=(i-1)(f_{i-1}+f_{i-2})$。

考虑一共有 $i$ 有奶牛，第 $i$ 头奶牛可以随便去占前 $i-1$ 头奶牛的位置，假设他站在了第 $j$ 头奶牛的位置。接下来，我们分类讨论：

• 第 $j$ 头奶牛站在第 $i$ 头牛的位置：此时有 $(i-1) \times f_{i-2}$ 种情况。
• 否则，我们可以把第 $j$ 头牛“染成”第 $i$ 头牛一样的牛（这样是等价的），这样就有 $(i-1)\times f_{i-1}$ 种情况。

当然，你也可以拿容斥推出这个不甚美观的式子

$$f_n =\sum _{i=0} ^n (-1)^i C_n ^i(n-i)! = \sum _{i=0} ^n (-1)^i \frac{n!}{i!} $$