菜王的 blog

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

$2m > n$ 显然无解，判掉。

首先考虑，对于一个 $> 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)$。代码在这里。