[GDKOI2023 提高组] 错排 题解

· · 题解

可能更好的阅读体验

非常好 Counting，使我滨州发光旋转。

首先考虑，对于一个 $> m$ 的数，如果它填到了左边，那么它所对应的位置就没有限制了。所以考虑在 $> m$ 的数中选择 $m$ 个，有序地填到左边，右边 $n - m$ 个位置就有 $m$ 个没有限制，剩下 $n - 2m$ 个位置有限制。 如果我们设 $f_{i, j}$ 为一个长为 $i + j$ 的序列，前面 $i$ 个位置没有限制，后面 $j$ 个位置有限制的方案数，则答案为 $m!\binom{n - m}mf_{m, n - 2m}$，现在我们的目标就变为快速求出 $f_{i, j}$。 考虑推导出递推式。按照传统错排问题的思路，考虑填一个有限制的位置对应的数。考虑两种情况： 1. 其对应的数填到了一个无限制的位置，则这个有限制的位置变为无限制的位置，被填到的那个位置被移除，相当于少了一个有限制的位置，无限制的位置个数不变，方案数为 $i \times f_{i, j - 1}$。 2. 其对应的数填到了另外一个有限制的位置，则这个有限制的位置变为无限制的位置，被填到的那个位置被移除，相当于少了两个有限制的位置，无限制的个数多了一个，方案数为 $(j - 1) f_{i + 1, j - 2}$。 于是可以 $O(n^2)$ 预处理 $f_{i, j}$。 尝试填一个无限制的位置对应的数得到另一个递推式，考虑两种情况： 1. 其对应的数就填在这个位置，则不产生任何贡献，方案数为 $f_{i - 1, j}$。 2. 钦定其对应的数不能填在这个位置，这个无限制的位置变为有限制的位置，方案数为 $f_{i - 1, j + 1}$。 整合一下得到两个递推式： $$ f_{i, j} = i \times f_{i, j - 1} + (j - 1) f_{i + 1, j - 2}\\ f_{i, j} = f_{i - 1, j} + f_{i - 1, j + 1}\\ $$ 将第二个递推式代入第一个递推式的 $f_{i + 1, j - 2}$ 中，得到： $$ f_{i, j} = i \times f_{i, j - 1} + (j - 1)(f_{i, j - 2} + f_{i, j - 1})\\ f_{i, j} = (j - 1)f_{i, j - 2} + (i + j - 1)f_{i, j - 1}\\ f_{i, j + 2} = (j + 1) \times f_{i, j} + (i + j + 1) f_{i, j + 1}\\ $$ 所以如果知道了 $f_{i, j}, f_{i, j + 1}$ 可以 $O(1)$ 求出 $f_{i, j + 2}$。根据最开始的第二个递推式，有： $$ f_{i + 1, j} = f_{i, j} + f_{i, j + 1}\\ f_{i + 1, j + 1} = f_{i, j + 1} + f_{i, j + 2}\\ $$ 将 $f_{i, j + 2}$ 代入，得： $$ f_{i + 1, j + 1} = (j + 1) \times f_{i, j} + (i + j + 2) f_{i, j + 1}\\ $$ 所以如果知道了 $f_{i, j}, f_{i, j + 1}$ 可以 $O(1)$ 求出 $f_{i + 1, j}, f_{i + 1, j + 1}$。 我们也可以手动解方程回推，知道 $f_{i, j}, f_{i, j + 1}$ 可以 $O(1)$ 求出 $f_{i, j - 1}$ 以及 $f_{i - 1, j}, f_{i - 1, j + 1}$： $$ f_{i - 1, j} = \frac{(i + j + 1)f_{i, j} - f_{i, j + 1}}i\\ f_{i - 1, j + 1} = \frac{f_{i, j + 1} - (j + 1)f_{i, j}}i\\ f_{i, j - 1} = \frac{f_{i, j + 1} - (i + j) f_{i, j}}j\\ $$ 综上所述，我们可以维护 $(f_{i, j}, f_{i, j + 1})$，并在 $O(1)$ 的时间复杂度内支持 $i \to i \pm 1, j \to j \pm 1$ 四种操作。于是将询问离线下来，上莫队即可，时间复杂度为 $O(T \sqrt n)$。[代码](https://www.luogu.com.cn/paste/xq7nwsj1)在这里。