题目链接：「THUPC 2023」Freshman Dream

「THUPC 2023」Freshman Dream 题解

题目重述

给定一个 $n \times n$ 的 01 矩阵 $A$，需要构造一个 01 矩阵 $B$，满足：

$$AB \equiv A \odot B \pmod 2$$

其中 $AB$ 是普通矩阵乘法（模 2），$\odot$ 是逐元素乘积（Hadamard 积）。并且要求 $B$ 中恰好有 $k$ 个 1。若不存在则输出 -1。

---

解法分析

1. 条件转化

将 $AB = A \odot B$ 写成元素形式，对任意 $i,j$：

$$\sum_{l=1}^n A_{i,l} B_{l,j} \equiv A_{i,j} B_{i,j} \pmod 2$$

移项得：

$$\sum_{l=1}^n A_{i,l} B_{l,j} + A_{i,j} B_{i,j} \equiv 0 \pmod 2$$

注意左边求和项中包含了 $l=i$ 的项 $A_{i,i}B_{i,j}$，与最后的 $A_{i,j}B_{i,j}$ 合并：

$$\sum_{l\neq i} A_{i,l} B_{l,j} + (A_{i,i}+A_{i,j})B_{i,j} \equiv 0 \pmod 2$$

固定列 $j$，令向量 $b_j = (B_{1,j}, B_{2,j}, \dots, B_{n,j})^T$，则上式等价于：

$$(A + \operatorname{diag}(A_{1,j}, A_{2,j}, \dots, A_{n,j})) \cdot b_j \equiv 0 \pmod 2$$

因此，对于每一列 $j$，$b_j$ 必须是矩阵 $M_j = A + \operatorname{diag}(A_{1,j},\dots,A_{n,j})$ 的零空间（核）中的一个向量。不同列之间相互独立，所以问题转化为：

• 对每个 $j=1..n$，求齐次线性方程组 $M_j x = 0$ 的所有解向量；
• 从每个解空间中选择一个向量作为第 $j$ 列，使得所有列中 1 的总数恰好为 $k$。

---

2. 子问题求解

对于每个 $j$，矩阵 $M_j$ 是 $n \times n$ 的 01 矩阵。我们用高斯消元（异或消元）求出其行最简形，并找出自由变量。设自由变量个数为 $f$，则解空间大小为 $2^f$。枚举所有自由变量的取值，即可得到所有解向量，并记录每个解的 1 的个数。

由于 $A$ 是随机生成的，矩阵通常满秩（或接近满秩），所以 $f$ 很小，枚举是可行的。最坏情况下 $f$ 可能达到 $n$，但题目数据保证随机，且 $n=100$，即使最坏也可用优化，但实际运行良好。

---

3. 全局背包合并

设 $dp[i][s]$ 表示考虑了前 $i$ 列后，已经选用的 1 的总数为 $s$ 是否可行（$0 \le s \le k$）。
初始化 $dp[0][0] = \text{true}$。
对于第 $i$ 列，设其所有可能解向量的重量集合为 $W_i$（包含重复重量，去重或不区别均可，因为重量相同向量不同但只影响计数，我们只需知道重量存在即可，但后续回溯需要知道具体解，所以需要存储每个重量对应的一个解向量）。转移时：

$$dp[i][s] = \bigvee_{w \in W_i} dp[i-1][s-w]$$

同时记录转移来源（即当前列选择的重量 $w$），以便最后回溯构造矩阵。

---

4. 回溯构造

若 $dp[n][k]$ 为真，则从 $i=n$ 开始，根据记录的 $w_i$ 取出第 $i$ 列对应的解向量，然后 $k \leftarrow k - w_i$，继续向前。最终得到矩阵 $B$。

若 $dp[n][k]$ 为假，输出 -1。

---

复杂度分析

• 对每一列做高斯消元：$O(n^3)$，$n=100$，共 100 列，约 $10^8$ 次位运算，但可用 bitset 优化，实际很快。
• 枚举解向量：$O(2^f \cdot n)$，由于随机矩阵满秩，$f$ 通常为 0 或很小，可忽略。
• DP：状态数 $n \times k$，转移时枚举重量集合，重量集合大小通常不大，总复杂度 $O(n \cdot k \cdot \text{avgW})$，可行。

---

Code:

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

int n, m;
int a[N][N];
bitset<N> p[N];                // 高斯消元过程中的矩阵行
vector<int> f[N][N * N];       // f[i][w] 存储第 i 列重量为 w 的一个解向量
int g[N], h[N][N * N];         // h[i][s] 记录 DP 路径
int A[N][N];                   // 最终的 B

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]);

    memset(h, -1, sizeof(h));
    h[0][0] = 1;

    for (int col = 1; col <= n; ++col) {      // 处理第 col 列
        // 构造矩阵 M = A + diag(A[1][col], ..., A[n][col])
        for (int i = 1; i <= n; ++i) {
            p[i].reset();
            for (int j = 1; j <= n; ++j)
                p[i][j] = a[i][j] ^ (i == j ? a[i][col] : 0);
        }

        // 高斯消元（异或）
        for (int i = 1; i <= n; ++i) {
            int pivot = -1;
            for (int j = i; j <= n; ++j)
                if (p[j][i]) { pivot = j; break; }
            if (pivot == -1) continue;
            swap(p[i], p[pivot]);
            for (int j = 1; j <= n; ++j)
                if (j != i && p[j][i])
                    p[j] ^= p[i];
        }

        // 找出自由变量对应的列号
        vector<int> freeCols;
        for (int j = 1; j <= n; ++j) {
            bool hasPivot = false;
            for (int i = 1; i <= n; ++i)
                if (p[i][j]) { hasPivot = true; break; }
            if (!hasPivot) freeCols.push_back(j);
        }

        int fcnt = freeCols.size();
        memset(g, 0, sizeof(g));
        // 枚举自由变量的所有取值 (2^fcnt)
        for (int mask = 0; mask < (1 << fcnt); ++mask) {
            vector<int> sol(n + 1);
            // 先填自由变量
            for (int idx = 0; idx < fcnt; ++idx)
                sol[freeCols[idx]] = (mask >> idx) & 1;
            // 回代求主变量
            for (int i = 1; i <= n; ++i) {
                int pivotCol = -1;
                for (int j = 1; j <= n; ++j)
                    if (p[i][j]) { pivotCol = j; break; }
                if (pivotCol == -1) continue;
                int val = 0;
                for (int j = pivotCol + 1; j <= n; ++j)
                    val ^= (p[i][j] & sol[j]);
                sol[pivotCol] = val;
            }
            // 计算重量
            int cnt1 = 0;
            for (int i = 1; i <= n; ++i) cnt1 += sol[i];
            // 记录该重量的一个解向量（保留首次出现的即可）
            if (!g[cnt1]) {
                g[cnt1] = 1;
                f[col][cnt1] = sol;
            }
        }

        // DP 合并
        for (int s = 0; s <= m; ++s) {
            for (int w = 0; w <= n && w <= s; ++w) {
                if (g[w] && ~h[col - 1][s - w]) {
                    h[col][s] = w;
                    break;
                }
            }
        }
    }

    if (!~h[n][m]) {
        puts("-1");
        return 0;
    }

    puts("1");
    vector<int> chosenW(n + 1);
    for (int i = n, cur = m; i >= 1; --i) {
        chosenW[i] = h[i][cur];
        cur -= chosenW[i];
    }

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            A[i][j] = f[j][chosenW[j]][i];

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            printf("%d%c", A[i][j], " \n"[j == n]);
    }

    return 0;
}

其他人错误的方面：

1.高斯消元中主元列的选取和自由变量的处理；
2.分组背包的状态转移和回溯；
3.无解情况的判断。