ARC188D Mirror and Order 题解

很强的转化。

先把一些无解的情况判掉。

我们肯定是考虑第一列和第三列的相同的数，不同的数的排名关系是确定的。

假定 $b$ 序列已知，我们考察建图。

如果第 $i$ 行第一列等于第 $j$ 行第三列，那么如果 $a_i<b_j$ 连边 $i$ 向 $j$ 否则连边 $j$ 向 $i$。

观察这张图的性质，我们注意到这个图每个点的度数为 $2$，把其看成无向图，每一个连通分量都是环。

显然，不能出现自环，我们还注意到，如果一个环，它的边定向是 $a\to b\to c\to \cdots\to a$，那么肯定无解，因为中间的数不能分配。

现在考虑原问题含有序列 $a,b$，$a$ 序列告诉了我们每个点是走出 $i$ 还是走入 $i$，我们把走出 $i$ 的标记为白点，走入 $i$ 的标记为黑点。

如果一个连通分量里所有点的颜色都相同，那么无解，否则有解。

考虑 $b$ 序列已经告诉了我们一些边，我们现在相当于把剩下的边连上，使得不存在同色环。

一共有四类情况：

如果环不合法直接判掉，剩下我们设 $B$ 表示全黑链的个数，$W$ 表示全白链的个数，$G$ 表示黑白皆有的链的个数。

我们把这些看成点，相当于需要连边，使得不存在全黑全白的环。

我们考虑那些同色极长段，假设有 $b$ 个这样的全黑极长段，$w$ 个这样的全白极长段。

先考虑把黑白皆有的形成一些环，再插入黑白点，这部分的方案数是 $G!$，可以想象到，因为一个点一开始有 $G$ 种选择方案，可以选自己，相当于自己这条链的起点连向终点，依次递推。

考虑构造出 $w$ 个这样的全白极长段，相当于把 $W$ 分成 $w$ 份，这部分方案数就是先把 $W$ 个点排列，但是注意到我们不区分这 $w$ 份，所以方案数为 $\frac{W!\binom {W-1}{w-1}}{w!}$。

我们记 $F(W,w)$ 表示上述的方案。

现在考虑插入黑白点，我们先把白点接上去，设有 $s$ 个后面接黑点，那么剩下都接黑白皆有。

这部分的方案数就是两个下降幂相乘，$\binom w sb^{\underline{s}}G^{\underline{w-s}}$。

于是我们只需要考虑黑点怎么接了，要么接白点，要么接黑白皆有，而且接白点不能接之前那些接黑白皆有的。

所以这部分的方案数是 $(G+s)^{\underline b}$。

于是枚举 $s,w,b$ 答案就是下面部分：

容易做到 $O(n^2)$，发现是卷积可以做到 $O(n\log n)$。

参考了官方题解。