n*n 的自然数矩阵 A,B, 其中 A 满秩. 求 A 的行向量到 B 的行向量的完美匹配, 使得用 B 的任意一行替换 A 的对应行, 其他行保持不变, 矩阵仍满秩, 或报告无解. 有解输出字典序最小的方案. (1 ≤ n ≤ 300, 所有数 ≤ 10^4) 一开始理解错了题意, 以为要求 2^n 种替换方式均满秩.
B[j] 可以替换 A[i] <=> B[j] 不能被除 A[i] 以外的行线性表出
用 A 的行向量线性表出 B[j] 的方式是唯一的. 所以, 上述条件等价于以 A 的行向量为基底求出 B[j] 的坐标, 第 i 维非 0.
设 CA = B, 根据矩阵乘法的某个意义, C 的第 i 行是 B 的第 i 行以 A 的行向量为基底的坐标. 那么, 求出 C = BA^-1, 当且仅当 C[j][i] != 0, 从 A[i] 向 B[j] 连边, 求二分图的完美匹配. 方便起见, 可以在模意义下对矩阵进行运算.
题面中说 "为了避免麻烦, 如果有多种可能的答案, 请给出字典序最小的那一组", 分明是为了增加难度嘛......
我的想法是从最后一个点开始, 逆序增广. 看了 Discuss, 和标程错到一块去了......
一个可以用于 hack 的二分图:
0 1
1 0
1 2
2 0
2 1
2 21 0 2, 上面的算法跑出来的是1 2 0. 最后一轮增广, 2 为了和 0 匹配, 修改 1 的对象为 2, 使结果变差.
一个正确的 O(n^3) 解法: 跑一遍匈牙利. 结束后图中没有交错路, 但是可以有交错环. 把环上的边在匹配中的存在性取反, 得到另一个最大匹配. 所有其他的最大匹配都可以用一次或多次这种操作得到. 从前往后, 为每个点贪心地寻找使该点的对象尽量小的交错环, 然后从图中删掉这个点的对象. 写起来和匈牙利的 DFS 差不多.
typedef long long ll;
const int MOD = 1e9 + 7, inf = 1e9, N = 300;
int n, A[N][2*N], B[N][N];
ll fpm(ll x, int n)
{
ll y = 1;
for (; n; n >>= 1, (x *= x) %= MOD)
if (n & 1)
(y *= x) %= MOD;
return y;
}
struct Hungary
{
bool adj[N][N];
int T, p[N], q[N], vis[N];
bool dfs(int x, int z)
{
rep (y, 0, n) if (adj[x][y] && vis[y] < T)
{
vis[y] = T;
if (p[y] == z || dfs(p[y], z))
return q[p[y] = x] = y, true;
}
return false;
}
bool main()
{
int ans = 0;
memset(p, -1, sizeof(int)*n);
rep (i, 0, n)
{
++T;
ans += dfs(i, -1);
}
if (ans != n) return false;
rep (i, 0, n)
{
++T;
dfs(i, i);
vis[q[i]] = inf;
}
return true;
}
} H;
bool inverse()
{
rep (i, 0, n)
{
int r = i;
while (r < n && !A[r][i]) ++r;
if (r == n) return false;
if (r != i) swap(A[r], A[i]);
r = fpm(A[i][i], MOD-2);
per (j, 2*n-1, i) A[i][j] = 1LL * A[i][j] * r % MOD;
rep (j, 0, n) if (j != i)
{
r = A[j][i];
rep (k, 0, 2*n)
A[j][k] = ((A[j][k] - 1LL * r * A[i][k]) % MOD + MOD) % MOD;
}
}
return true;
}
int main()
{
scanf("%d", &n);
rep (i, 0, n) rep (j, 0, n) scanf("%d", &A[i][j]);
rep (i, 0, n) rep (j, 0, n) scanf("%d", &B[i][j]);
rep (i, 0, n) A[i][i+n] = 1;
if (!inverse()) return puts("NIE"), 0;
rep (i, 0, n) rep (j, 0, n)
{
A[i][j] = 0;
rep (k, 0, n) A[i][j] = (A[i][j] + 1LL * B[i][k] * A[k][j+n]) % MOD;
if (A[i][j]) H.adj[j][i] = true;
}
if (H.main())
{
puts("TAK");
rep (i, 0, n) printf("%d\n", H.q[i] + 1);
}
else
puts("NIE");
return 0;
}