ABC214G – Three Permutations 题解
这题做了一万年，最后也算是想出了一个比较强大的模型转换。。。
给定两个大小为 $N$ 的排列 $P,Q$ ，询问满足以下条件的排列 $R$ 的数量：
- 对于任意 $i\in [1, N]$ 均满足 $R_i\neq P_i \cap R_i\neq Q_i$ 。
$N\leq 3000$ 。
看到这题很容易想到AtCoder上曾经有一个本题的弱化版本：ABC172E – NEQ，题解参考本文。
所以，对于本题，我们也容易想到一个基于容斥原理的做法：枚举有 $i$ 个位置违背题目要求（即存在 $i$ 个位置 $x$ 使得 $R_x=P_x$ 或者 $R_x=Q_x$），假设此时的方案数为 $F_i$ ，那么本题的结论就是：
那么本题的核心问题就是 $F_i$ 的求解。由于同时有排列 $P$ 和排列 $Q$ 两个限制，我们不妨转化为一个图论模型：有一个 $N$ 个点的图，对于违背条件的点对 $(P_i,Q_i)$ 连边。那么 $F_i$ 就相当于是一个有 $i$ 条边的图，每条边都必须选择一个顶点（被选中的顶点表示到底是 $P_i=R_i$ 还是 $Q_i=R_i$）的方案数。
观察一下这个建图方式，不难发现如果我们对于所有的 $j\in [1,N]$ 建立 $(P_j,Q_j)$ 边，那么整个图一定由一堆环构成，所以我们可以把这些环先找出来，然后对于每个环而言都构成一个独立的子问题：假设有一个大小为 $i$ 的环图，我们需要在这个环图中选 $j$ 条边，然后对于每条边再选择一个对应的顶点，记方案数为 $G_{i,j}$ ，如果我们能够求出所有的 $G_{i,j}(j\in [0,i])$ ，那么就有一个多项式形式的问题转换（这个多项式转换也可以通过dp实现，时间复杂度 $O(N^2)$ ）：
这个多项式可以通过启发式合并+FFT的方法在 $O(N\log^2N)$ 的时间复杂度内求出，因此我们现在只需要求解 $G_{i,j}$ 。
上面的这些分析在有经验的情况下其实不难，也算比较套路，但是最后这一步求解 $G_{i,j}$ 着实没有那么简单，我思考了接近整整一天。我们复述一下这个子问题：
定义 $G_{i,j}$ 表示：在一个大小为 $i$ 的环图中，选择 $j$ 条边，然后对于我们选定的每条边都再选择它两个顶点中的一个，这样选择的方案数。对于 $j\in [0,i]$ 均需要求解。
比如 $G_{3,2}$ ，我们用 $A,B,C$ 依次表示 $3$ 个顶点，$1,2,3$ 依次表示 $3$ 条边，那么整个图就可以表示为 $A1B2C3$ ，有以下几种选择方案：$A1B2,A1C2,B1C2,B2C3,B2A3,C2A3,C3A1,C3B1,A3B1$ 一共 $9$ 种。
注意到我们其实不用区分点和边（因为任意一条边必定对应了一个唯一的点），所以这实际上等价于另一个问题：一个大小为 $2i$ 的环图中存在恰好 $j$ 对匹配点（匹配点对必定相邻，于是可以看作一对点和边的组合）的方案数，也就是环图上的K匹配问题，这可以在OEIS上找到很多现成的结论，在这里我给出一个组合方法的式子：
为什么是这个式子？因为我只会通过组合意义解释这个式子，并且这个式子可以用来解决另一个等价命题：在一个大小为 $i$ 的环上有 $j$ 个黑色节点和 $i-j$ 个白色节点，任意两个黑色节点不相邻的方案数。（等价于一个大小为 $i$ 的环图中存在恰好 $j$ 对匹配点的方案数，这是因为对于每一对匹配点，如果我们都只看位于“右侧”的那个点，那么这些点一定不会相邻）
不妨先思考一个简化命题：在一个大小为 $i$ 的线段上有 $j$ 个黑色节点和 $i-j$ 个白色节点，任意两个黑色节点不相邻的方案数。这是个经典问题：“不相邻的组合数”，答案是 $\binom{i-j+1}{j}$ ，记为 $h_{i,j}$ 。在组合意义上也很容易解释：因为任意两个黑色节点不相邻，所以我们先在所有 $i$ 个节点中取出 $j-1$ 个，然后在剩余的节点中随便取 $j$ 个，最后再将我们取出的 $j-1$ 个节点插入会选出的 $j$ 个节点之间。
回到环上，不难发现圆环相当于增加了一个限制：不能同时选择第一个和最后一个节点。于是，利用容斥原理，圆环上的方案数就是 $h_{i,j}-h_{i-4,j-2}$ 。$h_{i-4,j-2}$ 就是我先确定必选第 $1$ 个和第 $i$ 个节点，由于不能选择相邻的，所以第 $2$ 个和第 $i-1$ 个节点不能选择，只剩下 $i-4$ 个空位，还需要选出 $j-2$ 个。
于是，我们就解决了本题。而且注意到我们的解法时间复杂度是 $O(N\log^2N)$ ，所以本题的数据范围事实上还可以加两个零。
这题做的相当艰难，整个问题的解决经历了一堆模型转换：原始命题->子问题->环图k匹配问题->圆环不相邻组合数，总算是把这个问题转化为了经典模型。。。
AC代码 。