原题：https://codeforces.com/problemset/problem/1980/E
题目大意：给你一个 n x m 的矩阵，包含1到n*m的整数排列
n 个整数的排列是一个数组，包含从 1 到的所有整数。
例如，数组 [1], [2,1,3], [5,4,3,2,1] 是排列
而数组 [1,1], [100], [1,2,4,5] 不是排列
你可以对这个矩阵进行无限次操作的 行变换 或者 列变换。
给你原始矩阵 a 和矩阵 b 。你的任务是确定是否可以通过给定的运算将矩阵 a 变换为矩阵 b
解析
首先要知道这么一个数学的事实：对于一个矩阵，在单独一次操作中，行变换并不会改变列，而列变换也不会改变行。
我们选取矩阵中某个元素为e，然后选取该元素所在的行与列，我们把行内的元素叫做排列R，而列内的元素叫做C。
当对这个矩阵任意次行列变换后：
R内所有元素的行编号仍相等，因为列变换不会改变行
C内所有元素的列编号仍相等，因为行变换不会改变列
还注意到：行列变换会打破排列之间的顺序，但是并不会改变排列元素的集合
由此便可以这样思考问题，矩阵a可以通过行列变换变成矩阵b的条件是：对于某个元素，我们对矩阵进行任意次的行列变换后，这个元素在a矩阵的 排序后的行列排列 与这个元素在b矩阵的 排序后行列排列 仍然相等。
开两个pair数组pa, pb，分别记录数字在a矩阵和b矩阵中的位置。遍历 1~n*m 寻找每个数字它在a矩阵和b矩阵中的排序后的行列排列是否相等。
时间复杂度
比较容易想到的排序方法是 开 vector<vector<int>> sax, say, sbx, sby 四个数组记录已经排好的序列，然后在读入矩阵后排序一次。
sax[i] 表示在a中取第i行的排列 (已排序）
say[i] 表示在a中取第i列的排列（已排序）
然后对于每个数字的位置，遍历检查 sax 和 sbx, say 与 sby 是否相等
然而，使用这种办法在遍历 1~n*\m 个数字的时候，最坏的总体时间复杂度是会达到 **O(n^2 * m^2) **的
想办法优化时间复杂度，对行列排列进行散列化是一个可能的方案
散列化
我们的目标是通过散列化把比较排列的时间复杂度降到O(1)，那么必须用某个哈希值代替掉vector<vector<int>> 中的 vector<int>
由于C++并没有vector哈希函数的模版，因此需要手动对行列进行散列操作，其中一种容易想到的操作是把排序后的行列排列变为字符串，再用string哈希进行散列操作
最后，我们遍历 1~n*\m 个数字，检查两个矩阵里面这个数字所在排列的哈希值是否相同即可。至此，时间复杂度为 O(nm)
代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 2e5+10;
typedef long long ll;
#define x first
#define y second
typedef pair<int, int> P;
vector<vector<int>> a, b;
vector<P> pa(mod), pb(mod);
//sax[i] 表示在a中取第i行的排列的哈希值（已排序）
//say[i] 表示在a中取第i列的排列的哈希值（已排序）
vector<size_t> sax, say;
vector<size_t> sbx, sby;
void solve() {
int n, m;
cin >> n >> m;
pa.clear();
a.resize(n);
for (int i = 0; i < n;i++) {
a[i].resize(m);
for (int j = 0; j < m; j++) {
cin >> a[i][j];
pa[a[i][j]] = {i, j};
}
}
pb.clear();
b.resize(n);
for (int i= 0; i< n;i++) {
b[i].resize(m);
for (int j = 0; j < m; j++) {
cin >> b[i][j];
pb[b[i][j]] = {i, j};
}
}
sax.resize(n);
say.resize(m);
for (int i = 0; i < n; i++) {
vector<int> r(m);
for (int j = 0; j < m; j++) {
r[j] = a[i][j];
}
sort(begin(r), end(r));
stringstream ss;
for (auto it : r) ss << it;
sax[i] = hash<string>{}(ss.str());
}
for (int i = 0; i < m; i++) {
vector<int> r(n);
for (int j = 0; j < n; j++) {
r[j] = a[j][i];
}
sort(begin(r), end(r));
stringstream ss;
for (auto it : r) ss << it;
say[i] = hash<string>{}(ss.str());
}
sbx.resize(n);
sby.resize(m);
for (int i = 0; i < n; i++) {
vector<int> r(m);
for (int j = 0; j < m; j++) {
r[j] = b[i][j];
}
sort(begin(r), end(r));
stringstream ss;
for (auto it : r) ss << it;
sbx[i] = hash<string>{}(ss.str());
}
for (int i = 0; i < m; i++) {
vector<int> r(n);
for (int j = 0; j < n; j++) {
r[j] = b[j][i];
}
sort(begin(r), end(r));
stringstream ss;
for (auto it : r) ss << it;
sby[i] = hash<string>{}(ss.str());
}
for (int i = 1; i <= n*m; i++) {
if (!(sax[pa[i].x] == sbx[pb[i].x] && say[pa[i].y] == sby[pb[i].y])) {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while (t--) solve();
return 0;
}