AT_agc057_e

_edge_ · 2025-01-26 14:58:35 · 个人记录

模拟赛出了这题，怎么回事捏。

先思考只有 0,1 的情况怎么做。

手玩一下大概操作就是把所有行的 0 个数求出来，然后按照这个个数对所有行进行排序，另一个操作也一样。

具体的，比方说，我们求出第 i 行的 0 个数为 r_i，那么对于一次对第 i 行进行排序相当于是把 0 都提到前 r_i 个，然后对列的排序，相当于是在把 0 都向上拿，也就相当于对 r 进行排序。

我们令 r_i 表示第 i 行的 0 的个数，c_i 表示第 i 列的 0 的个数，可以明确的是只要这个表格内的 r 和 c 与目标表格的 r 和 c 排序之后分别相同，那么就是 ok 的。

上面的条件是充分并且必要的，原因是，如果满足他们的 A 一定都能够排成 B，如果有一行不满足就不合法了，一列也是一样的。

那么对于 0,1 的情况，我们求出目标表格 r 序列和 c 序列，尝试随意重排他们就可以了，但是对于 r 和 c 的一种重排为啥就一定对应一种方案捏（这个证明很抽象，我没怎么看懂）。

这个问题如果忽略题目中的条件是不可做的，并且大部分情况都不是唯一的，比方说是下面这种情况。

* 是没有意义的，就是上面一行表示每一列的 0 的个数，左边一列表示每一行 0 的个数。

简单的证明就是，存在是必然的，因为你可以交换 B 矩阵的行或者列，唯一也是必然的，因为你可以把它交换为 B，B 唯一的话交换回去得到的也是唯一的！

因此，我们的答案就是，每一行 0 的个数求出来重排一下，每一列 0 的个数求出来重排一下！注意到 0 的个数有可能相同，所以要稍微处理一下。

那么考虑值域为 [0,9] 的情况，我们认为，对于 \le k 的点我们标记为 0，对于 > k 的点我们标记为 1，只要对于所有的 k 都满足就可以了。

我们尝试换一种描述方式，如果说能够重排的话就是存在两个排列 p,q，满足 A_{i,j}=B_{p_i,q_j}。

唯一可能出问题的地方在于，我们如果钦定某个点 \le k，那么在之后的 k+1,k+2, \cdots , 9 就也得满足小于等于他们，如果随意排列的话就可能会出问题。

我们把条件写出来，大概是 B_{p^k_i,q^k_j} \le k 能够得到 B_{p^{k+1}_i,q^{k+1}_j} \le k+1，我们可以做这样的操作，p^k \times inv(p^{k-1})，也就是相当于乘个逆排列，最终的目的是让每一个 k 变得互相独立，即 B_{i,j} \le k 得到 B_{p^k_i,q^k_j} \le k+1。

这样就很不错，我们可以枚举每一个 k 来计数。

模拟赛里有一档分是 n \le 8，就可以直接暴力枚举 p 排列来处理掉，处理 q 排列是非常简单的。

考虑先枚举一个排列 p，然后我们可以得到 q 每个位置的范围。

我们令 A1_j 表示第 j 列，最大的满足 B_{A1_j,j} \le k-1。令 A2_i 表示第 i 行，最大的满足 B_{i,A2_i} \le k。容易观察到 A1 和 A2 都是单调不升的。

令，f_{i,j} 表示前 i 项，最大值为 j 的贡献总和，分别计算 p 和 q 的贡献就 ok 了，相信这一步 dp 不是特别困难。