题解：AT_agc057_e [AGC057E] RowCol/ColRow Sort

Rotating_Lines · 2025-11-20 21:56:17 · 题解

题解

困难题，花费大量时间才会。

注意到值域很小，我们考虑从此入手。假设现在只有 01 两种数，那么我们对一个 A 进行操作后会是什么样子？如果是先行后列，相当于我们对每一行按 0 的数量降序排序且把 0 放在每行最前面；如果是先列后行，相当于我们对每一列按 0 的数量降序排序且把 0 放在每行最前面。 一个 A 合法，肯定需要让其行和列分别构成的可重集相等，并且 A 的可重集和 B 的可重集也一定是相等的。说明我们对 B 进行一些行或列的交换能够得到 A。我们刻画一下这个东西，相当于如果一个 A 合法，当且仅当存在两个排列 p,q，满足 \forall i,j,A_{i,j}=B_{p_i,q_j}。这个东西的数量就是两个可重集的排列数相乘：

现在考虑拓展。对于值域 [0,9] 的时候我们还是先思考如何判断合法。注意到值域很小，于是我们考虑枚举值域，设当前枚举到 i，那么我们将所有小于等于 i 的看成 0，否则看成 1，然后去判断 01 矩阵是否合法。如果每个 i 都合法那么这个矩阵合法。我们还是考虑刻画这个条件，相当于是存在一组排列 (p_0,q_0,p_1,q_1,\dots,p_9,q_9)，满足 [A_{i,j}\le k]=\forall i,j,k,[B_{p_{k,i},q_{k,j}}\le k]。这个条件必要性显然，考虑充分性。就是说我们在考虑枚举值域 i 的时候，相当于在前面枚举 i-1 的基础上将变化的位置填上 i。这样填肯定是能对应一个合法的 A 的。于是现在我们就去考虑满足条件的排列组数，然后去掉重复的方案数。

直接做是困难的，我们考虑将每个条件独立。现在有 B_{p_{k,i},q_{k,j}}\le k\rightarrow B_{p_{k+1,i},q_{k+1,j}}\le k+1，为了让每个枚举的 k 独立出来，我们考虑去计数更好做的。本来我们每次的排列 (p_k,q_k) 是在 (p_{k-1},q_{k-1}) 的基础上得到的，现在我们考虑定义一个 p'_k={p_k\over p_{k-1}}，然后拿 p'_k 去限制，这样就把每个 k 独立出来了。现在的条件就变成了 B_{i,j}\le k\rightarrow B_{p'_{k,i},q'_{k,j}}\le k+1。

注意到 B 中 \le k 的部分是杨表，所以一个位置小于一个数的条件可以简化。设 a_i 表示 B 的第 i 行最后一个 \le k 的位置，b_j 表示第 j 列最后一个 \le k 的位置。现在我们就能将前面的条件继续转化：\forall j\le a_i,p'_i\le b_{q'_j}。考虑到 b 递减，所以当 q'_j 取最大值时限制最严，然后限制就变成了 p'_i\le b_{\max\limits_{j=1}^{a_i}q'_j}。我们令下面那一坨等于 c_i，如果我们知道了 c_i 就能对 p',q' 计数。

考虑 p'。因为 a_i 递减，所以 c_i 递减，b_{c_i} 递增。于是 p' 的个数就是 \prod\limits_{i=1}^nb_{c_i}-i+1。考虑 q'。如果有 c_i=c_{i-1} 说明 (a_{i},a_{i-1}] 中没有最大值，考虑区间内选第一个数答案是 c_i-1-(a_i-1)=c_i-a_i，后面依次少一。如果里面有最大值，考虑每个位置出现最大值是等价的，于是多乘一个 a_{i-1}-a_i 即可，因为剩下的就等价于没有最大值的填法。

对于这个东西我们就可以考虑 dp 了，设 f_{i,j} 表示前 i 个数，c_i=j 的方案数。转移就按照上面说的做即可，注意转移的贡献与 j 无关，于是考虑后缀和优化一下即可。时间复杂度 \mathcal O(nmV)。