题解：AT_abc214_g [ABC214G] Three Permutations

· · 题解

注意到题解区没有和我一样无脑的做法。

这个限制不大好直接做，所以我们考虑容斥。容斥有至少 k 个位置是不满足限制的，即总方案数就应该为：

ans=\sum_{k=0}^{n} (-1)^k \times dp_k \times (n-k)!

其中 dp_k 表示选出 k 个位置不满足限制的方案数，然后剩下的 n-k 个位置可以随便乱填。并且这 k 个位置选的数满足应该两两不相同且必须是 p_i,q_i 中的一个。

可以想到转图论，将每一对 p_i,q_i 之间连上无向边，问题就转化为选出 k 条边，每条边分配一个端点且一个点只可以分配给一条边的方案数。

注意到题目中有这样一句话：

p_i\neq p_j \ \ q_i\neq q_j\,(i\neq j)

表示每个点的度数最多为 2，则每个联通块的形态只有三种情况：链，环，自环。

进行分类讨论，设 f_{i,j} 为在长度为 i 的一条链上选 j 条边的方案数，g_{i,j} 为在长度为 i 的一个环上选 j 条边的方案数。

自环

很明显如果选它就只有一种方案，那么转移方程应该为：

dp_k=dp_k+dp_{k-1}

环

转移方程应该有：

dp_k=dp_k+dp_{k-j} \times g_{i,j}

我们考虑断掉一条边使它成为一条链。

形如下图：

如果我们不选这条断掉的边，方案数就应该是 f_{i,j}，如果要选这条边，新增的方案数就应该和这条链的头，尾被选择的情况有关。

具体来说，我们再设 t_{i,j,0/1,0/1} 表示在长度为 i 的一条链上选 j 条边，第一个点有没有被选，最后一个点有没有被选的方案数。

则有：

g_{i,j}=f_{i,j}+2\times t_{i,j-1,0,0}+t_{i,j-1,0,1}+t_{i,j-1,1,0}

如果第一个和最后一个都没有被选，则断边可以在这两个中间二选一，否则如果有一个已经被选，就只能选另外一个点。

特别地，g_{i,i}=2。

链

转移方程应该有：

dp_k=dp_k+dp_{k-j} \times f_{i,j}

对于 f 的转移，很明显有：

f_{i,j}=t_{i,j,0,0}+t_{i,j,0,1}+t_{i,j,1,1}+t_{i,j,1,0}

对于 t 的转移来说，如果 i=2，有：

t_{i,0,0,0}=t_{i,1,0,1}=t_{i,1,1,0}=1

如果 i>2，注意到其实第一个点的被选情况和我们新加入一个点的转移没有什么关系，设第一个被选情况为 flag，有：

t_{i,j,flag,0}=t_{i-1,j,flag,0}+t_{i-1,j,flag,1}+t_{i-1,j-1,flag,0} t_{i,j,flag,1}=t_{i-1,j-1,flag,0}+t_{i-1,j-1,flag,1}

不难理解，读者可以自行尝试一下。

处理完上述的转移以后，对每个联通块去跑一遍 dfs，处理出联通块的大小，根据联通块的类型直接带上述公式跑一遍背包就可以处理出来，然后直接容斥。

时间复杂度 O(N^2)。

code