错排是简单的。

排列组合是简单的。

但没关同步流。导致挂 $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!} $$

曾经我想过为什么 0 的阶乘要等于 1，现在不用想了，因为组合数写挂了。

思路

这个题的思路是简单的：组合数计算 $m$ 个不动点，剩下 $n-m$ 个点错排，乘法原理相乘即可。

考虑错排的柿子怎么推，容易发现只有错排长度这一个变量，故设 $f_i$ 表示长度为 $i$ 的序列错排的方案数，易得边界点 $f_1=0,f_2=1$，不妨设 $f_0=1$，对于组合排列问题的一种普遍推法就是手模排列找规律，得到错排公式:

$$f_i=(i-1)f_{i-1}f_{i-2}$$

最终答案即为

$$ans_{n,m}=\binom{n}{m}f_{n-m}$$

由于组合数计算涉及阶乘，所以预处理所有需要用到的阶乘即可，因为对质数取模，还需计算阶乘逆元。

注意： 0 的阶乘为 1，一定要预处理。

代码不给了。