[0] 约定
\(r_i = \sum\limits_{j = 1}^{m}[A_{i,j}\le k]\)
\(r^{'}_i = \sum\limits_{j = 1}^{m}[B_{i,j}\le k]\)
\(c_j = \sum\limits_{i = 1}^{n}[A_{i,j}\le k]\)
\(c^{'}_j = \sum\limits_{i = 1}^{n}[B_{i,j}\le k]\)
[1] 分析思路
[1.1] 分析操作
对于 \(A\)，若 \(\forall k,\{r_i|i\in[1,n]\} = \{r^{'}_i | i\in[1,n]\}\)，则先行再列的排序后 \(A=B\)。
同理，若 \(\forall k,\{c_j|j\in[1,m]\} = \{c^{'}_j | j\in[1,m]\}\)，则先列再行的排序后 \(A=B\)。
由此，对于每个 \(k\)，确定 \(10\) 对排列 \(p_{1\sim n},q_{1\sim m}\)，满足对于第 \(i^{th}\) 对排列，排序后 \(k = i^{th},r_i = r^{'}_{p_i},c_i = c^{'}_{q_i}\)。
[1.2] 转化限制
对于每对排列单独考虑，需要满足 \([A_{i,j}\le k] = [B_{p_i,q_j}\le k]\)。
对于 \(i^{th}\) 相邻的两对排列，需要满足 \(B_{p_i,q_j}\le k \rightarrow B_{p\circ p^{'}_i,q\circ q^{'}_j}\le k + 1\)。
更进一步，\([B_{i,j}\le k] = [j\le r'_i] = [i\le c'_j]\)。
于是有 \(P:\forall i, j,j\le r'_i, p_i\le c'_{q_j}\)。
排序，使 \(c',r'\) 单调不增（以下写作 \(c,r\)）。
\(P:\forall i, p_i\le c_{\max\limits_{j = 1}^{r_i}q_j}\)
发现只要符合 \(P\) 的排列就可以组合在一起。
[2] 如何计数
[2.1] DP 方程
发现需要计数的是满足以下条件的排列：
\(x_i = \max\limits_{j = 1}^{a_i}q_j\le m\)
\(p_i\le c_{x_{i}}\le n\)
考虑 DP 计数。
考虑与 树上异或 相似的分阶段计数。
令 \(f_{i,j}\) 代表 \(p_{1\sim i}\) 已确定，\(q_{a_{i} + 1\sim m}\) 已确定，且 \(x_i = j\) 的方案数。
发现可以在 \(f_{i - 1, j} \to f_{i,j}\) 的过程中计算 \(p_i\) 的贡献 \(j - (i - 1)\)。
可以在 \(i - 1\to i\) 的过程中计算 \(q_{a_{i} + 1\sim a_{i - 1}}\) 的贡献，用组合数算即可。
[2.2] 细节
就是无解或得到负数的情况。
[3] 后记
[3.0] 注意
以下全为作者自己口胡的，不要看，不要看！很可能是错的！
[3.1] 正文
好的，让我们从头开始。
考虑排序对 \(A\) 造成的影响，发现比较难想。
发现 \(B\) 必然已经有序。
减少限制，若 \(A_{i,j}\in[0,1]\)。
[3.1.2] 约定
\(r_i\) 代表第 \(i\) 行 \(1\) 的个数。
\(c_j\) 代表第 \(j\) 列 \(1\) 的个数。
结论：
若可重集 \(r_A=r_B,c_A=c_B\) 那么排序后 \(A,B\) 相同。
证明：
考虑排序对 \(A\) 造成的影响。
先行再列，相当于对 \(r_i\) 排序。
先列再行，相当于对 \(c_j\) 排序。
回到原题，\(A_{i,j}\in[0,9]\)。
[3.1.3] 约定
\(r_{k,i}\) 代表第 \(i\) 行 \([A_{i,j}\le k] = 1\) 的个数。
\(c_{k,j}\) 代表第 \(i\) 行 \([A_{i,j}\le k] = 1\) 的个数。
再次考虑排序的意义，发现因为对于每个 \(k\)，将 \(A\) 中元素视为 \([A_{i,j}\le k]\in[0,1]\)，发现对于每个 \(k\) 排序得到的最终 \(A_{k}'\) 与 \(A_{i,j}\in[0,1]\) 的情况等价。
考虑通过 \(k\) 个 \(A_{k}'\) 还原 \(A'\)，若 \(A_{k,i,j}'\) 为 \(1\) 说明 \(A'_{i,j}\le k\)，同理 \(0\) 代表 \(A'_{i,j}>k\)。
直接计数应该也可以，但明显时间复杂度有问题。
发现 \(k\) 与 \(k + 1\) 的关系并没有那么紧密，因为只需要保证
\[\forall i\in[1,n],j\in[1,m],k\in[1,9],r_{k,i}\ge r_{k-1,i},c_{k,j}\ge c_{k-1,j} \]即可。
[4] 参考资料
E - RowCol/ColRow Sort Editorial by evima
标签：le,limits,题解,sum,agc057,forall,排序,sim From： https://www.cnblogs.com/SkyMaths/p/17825647.html