「CEOI2023」Balance

感觉这种题天克我啊。。

题目给出了 \(S=2^k\) 的限制，让我们有一些奇怪的思考，再加上有 \(S=2\) 的部分分，我们可以考虑从 \(S=2\) 拓展到任意情况。故我们先研究 \(S=2\) 的情况。

我们对颜色建点，对于每一行的两种颜色之间连一条边。然后我们考虑钦定每一条边的方向以表示这一行的交换情况。那么显然合法的充要条件就是每个点的入度与出度之差不超过 \(1\)。据说，这是经典图论问题。我们可以将奇度点配对（其数量肯定为偶数），配对的两点之间连一条边。对这一个图跑欧拉回路，就可以得到合法的钦定结果了。也就是说 \(S=2\) 的情况下，任何矩阵都是满足条件的。

对于一种平凡的情况，我们考虑分成两部分，把每种颜色都均匀（左右相差不超过 \(1\)）地分配到两边。考虑每行分到左右的要恰好各一半，我们直接对每行建点，然后对此行所有颜色连边。容易发现在这种情况下的定向依然可以达到理想的要求。故对这个图进行以上相同的处理，即可完成均匀分配的目标。然后再递归分治两边即可。时间复杂度 \(\mathcal O(nS\log S)\)。注意建图的复杂度不能带有 \(T\)，否则是假的。