ARC188D Mirror and Order 题解

· · 题解

很强的转化。

Part 1 转化

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

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

假定 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 表示黑白皆有的链的个数。

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

Part 2 计数

我们考虑那些同色极长段，假设有 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 答案就是下面部分：

\begin{aligned} \frac{(G!)^2(G+s)!F(W,w)\binom w sF(B,b)b!}{(G-w+s)!(b-s)!(G+s-b)!} \end{aligned}

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

参考了官方题解。