ARC188D 题解

· · 题解

考虑给定 a, b 如何判定。

一个显然的事情是，2i - 1 和 2i 对应那 2n 个序列中两个开头为 i 的序列。所以 2i - 1 和 2i 不会同时出现在 a 或者 b 中。

若 2i - 1 出现在 a 中，2i 出现在 b 中，那么设 2i - 1 在 a 中出现的位置为 x，2i 在 b 中出现的位置为 y。设 c_i 为排序前的 n 个序列中的第 i 个序列的第 2 项，可以得到 c_x < c_y。反之，若 2i 出现在 a 中，2i - 1 出现在 b 中，设其出现位置分别为 x, y，可以得到 c_y < c_x。考虑拓扑排序判定，若 c_x < c_y 就连一条 x \to y 的有向边，那么 a, b 可行的充要条件是图中无环。

这种判定方式太蠢了，没办法计数。考虑观察性质。发现这个有向图中每个点的入度和出度之和都为 2，考虑把有向边看成无向边，图会变成若干个环，原来的有向图有环等价于在这个无向图的一个环中，所有边的方向都相同。不妨调换一下 (a_i, b_i) 的顺序使得 \left\lceil\frac{a_i}{2}\right\rceil = i，设 p_i = \left\lceil\frac{b_i}{2}\right\rceil，即把无向环看成有向环之后 i 的后继。那么无向边 (i, p_i) 的方向仅取决于 a_{p_i} \bmod 2：若 a_{p_i} \bmod 2 = 1，那么方向为 i \gets p_i，否则为 i \to p_i。至此我们发现环的所有边方向相同，当且仅当环上所有点的 a_i \bmod 2 相同。

回到原题，现在有些 p_i 不确定，即图由若干个链和环组成。对于环，若环上所有点的 a_i \bmod 2 相同那么直接输出 0，否则不用管。对于链，设 c_0 为链上所有点的 a_i \bmod 2 都 = 0 的链的个数，c_1 为链上所有点的 a_i \bmod 2 都 = 1 的链的个数，c_2 为链上所有点的 a_i \bmod 2 不全相等的链的个数。那么问题是将这些链组成环，要求不存在环上所有点的 a_i \bmod 2 相同的环。

考虑容斥，将 c_0 条链中的 i 条组成 k 个环，c_1 条链中的 j 条组成 l 个环，剩下随意。设 g_{i, j} 为 i 条链组成 j 个环的方案数，答案即为：

\sum\limits_{i = 0}^{c_0} \sum\limits_{j = 0}^{c_1} \sum\limits_{k = 0}^i \sum\limits_{l = 0}^j (-1)^{k + l} \binom{c_0}{i} \binom{c_1}{j} g_{i, k} g_{j, l} (c_0 - i + c_1 - j + c_2)!

其中 (c_0 - i + c_1 - j + c_2)! 为 c_0 - i + c_1 - j + c_2 条链组成若干个环的方案数。

设 f_i = \sum\limits_{j = 0}^i (-1)^j g_{i, j}，即所有方案的容斥系数之和，那么答案为：

\sum\limits_{i = 0}^{c_0} \sum\limits_{j = 0}^{c_1} \binom{c_0}{i} \binom{c_1}{j} f_i f_j (c_0 - i + c_1 - j + c_2)! 但是你可以发现当 $i \ge 2$ 时 $f_i = 0$，即当 $n \ge 2$ 时有偶数个环的置换和有奇数个环的置换个数相等，证明就是构造双射，一个偶排列交换 $p_1, p_2$ 后能对应一个奇排列。所以答案式子中 $i, j$ 只用枚举到 $1$。预处理阶乘后答案式子可以 $O(1)$ 计算，总时间复杂度 $O(n)$。 [code](https://atcoder.jp/contests/arc188/submissions/60187028)