题意 给定一个满秩的矩阵
\(A\) ，另一个矩阵
\(B\) 对于
\(A\) 的每个行向量
\(A_i\) 找到一个匹配
\(B\) 的行向量
\(B_{p_i}\) 使得
\(A_i\) 替换成
\(B_{p_i}\) 后的矩阵
\(A'\) 仍然满秩
Sol 如果
\(B_{p_i}\) 能替换
\(A_i\)，那么说明存在一个向量
\(\lambda\) 使得
\(\lambda \times A'=B_{p_i}\) 而
\(A\) 线性无关，只要
\(A\) 的元素表示
\(B_{p_i}\) 的线性组合中
\(A_i\) 的系数不为
\(0\) 就好了
所以只要求出系数矩阵
\(C\)，使得
\(C\times A=B\) 然后对于不为
\(0\) 的
\(C_{i,j}\)，将
\(j\) 向
\(i\) 连边，求这个二分图的字典序最小的完备匹配就好了
求
\(C\) 可以矩阵求逆实现，
\(C=B\times A^{-1}\) 求二分图的字典序最小的完备匹配，可以先跑一遍匈牙利算法
然后在这个基础上再跑一次增广，贪心的匹配最小的，只改变匹配比当前点大的匹配边
# include using namespace std;typedef long long ll;const int mod(10007);int a[305][605], b[305][305], d[305][305], c[305][305];int idx, n, ans, match[305], chos[305], cnt, vis[305];inline int Pow(int x, int y) { register int ret = 1; for (; y; y >>= 1, x = x * x % mod) if (y & 1) ret = ret * x % mod; return ret;}inline void GetInv() { register int i, j, k, inv, m = n + n; for (i = 1; i <= n; ++i) a[i][i + n] = 1; for (i = 1; i <= n; ++i) { for (j = i; j <= n; ++j) if (a[j][i]) { if (i != j) swap(a[i], a[j]); break; } inv = Pow(a[i][i], mod - 2); for (j = i; j <= m; ++j) a[i][j] = a[i][j] * inv % mod; for (j = 1; j <= n; ++j) if (i != j) for (inv = a[j][i], k = i; k <= m; ++k) a[j][k] = (a[j][k] - a[i][k] * inv % mod + mod) % mod; } for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) d[i][j] = a[i][j + n];}inline void GetEdge() { register int i, j, k; for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) for (k = 1; k <= n; ++k) (c[i][k] += b[i][j] * d[j][k] % mod) %= mod;}int Dfs(int u) { register int v; for (v = 1; v <= n; ++v) if (c[v][u] && vis[v] != idx) { vis[v] = idx; if (!match[v] || Dfs(match[v])) return chos[u] = v, match[v] = u, 1; } return 0;}int Change(int u, int rt) { register int v; for (v = 1; v <= n; ++v) if (c[v][u] && vis[v] != idx) { vis[v] = idx; if (!match[v] || (match[v] > rt && Change(match[v], rt))) return chos[u] = v, match[v] = u, 1; } return 0;}int main() { scanf("%d", &n); register int i, j; for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) scanf("%d", &a[i][j]); for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) scanf("%d", &b[i][j]); GetInv(), GetEdge(); for (i = 1; i <= n; ++i) ++idx, ans += Dfs(i); if (ans != n) return puts("NIE"), 0; puts("TAK"); for (i = 1; i <= n; ++i) ++idx, match[chos[i]] = 0, chos[i] = 0, Change(i, i); for (i = 1; i <= n; ++i) printf("%d\n", chos[i]); return 0;}