题目描述

给定三个 01 矩阵：$A$ ($n \times m$)，$B$ ($m \times p$) 和 $C$ ($n \times p$)。
它们之间的乘积运算定义如下（基于 GF(2) 域，即模 2 算术）：
$$C_{i,j} = \bigoplus_{k=1}^{m} (A_{i,k} \ \& \ B_{k,j})$$
其中 $\oplus$ 表示按位异或 (XOR) 运算，$\&$ 表示按位与 (AND) 运算。由于矩阵元素是 0 或 1，这等价于标准矩阵乘法在 GF(2) 上的定义：
$$C_{i,j} = \left( \sum_{k=1}^{m} A_{i,k} \cdot B_{k,j} \right) \pmod 2$$

现在，问题是进行这个乘法的“逆运算”或“除法”：给定矩阵 $A$ ($n \times m$) 和 $C$ ($n \times p$)，你需要找到一个 $m \times p$ 的 01 矩阵 $B$，使得 $A \times B = C$ （在上述 GF(2) 乘法定义下）。

如果不存在这样的矩阵 $B$，输出 “No”。
如果存在，输出 “Yes”，然后输出你找到的任意一个矩阵 $B$。

样例

输入 #1:

3 2 3
1 0
1 1
1 0
0 0 0
0 1 0
0 0 0

输出 #1:

Yes
0 0 0
0 1 0

说明：
$A = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 0 \end{pmatrix}$, $C = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix}$.
找到 $B = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$。
验证 $A \times B \pmod 2$:
$C_{1,1} = (1 \cdot 0 + 0 \cdot 0) \pmod 2 = 0$
$C_{1,2} = (1 \cdot 0 + 0 \cdot 1) \pmod 2 = 0$
$C_{1,3} = (1 \cdot 0 + 0 \cdot 0) \pmod 2 = 0$
$C_{2,1} = (1 \cdot 0 + 1 \cdot 0) \pmod 2 = 0$
$C_{2,2} = (1 \cdot 0 + 1 \cdot 1) \pmod 2 = 1$
$C_{2,3} = (1 \cdot 0 + 1 \cdot 0) \pmod 2 = 0$
$C_{3,1} = (1 \cdot 0 + 0 \cdot 0) \pmod 2 = 0$
$C_{3,2} = (1 \cdot 0 + 0 \cdot 1) \pmod 2 = 0$
$C_{3,3} = (1 \cdot 0 + 0 \cdot 0) \pmod 2 = 0$
结果等于给定的 $C$。

输入 #2:

3 2 3
1 0
1 1
1 0
1 0 0
0 1 0
0 0 1

输出 #2:

No

算法 (高斯消元 / 线性基)

时间复杂度 $O(\frac{n \cdot m \cdot (m+p)}{w})$ 或 $O(n^2 \cdot (m+p)/w)$

思路分析

1. 理解问题: 核心是解矩阵方程 $A \times B = C$ 在 GF(2) 域上。$A$ 和 $C$ 已知，$B$ 是未知的。

2. 按列分解: 矩阵乘法的定义告诉我们，结果矩阵 $C$ 的第 $j$ 列 $C_{*,j}$ 是由矩阵 $A$ 乘以 $B$ 的第 $j$ 列 $B_{*,j}$ 得到的。即：
   $$A \times B_{*,j} = C_{*,j}$$
   这里 $B_{*,j}$ 是一个 $m \times 1$ 的列向量，$C_{*,j}$ 是一个 $n \times 1$ 的列向量。

3. 线性方程组: 对于 $B$ 的每一列 $B_{*,j}$ (共 $p$ 列)，我们都有一个独立的线性方程组 $A \times x = c$，其中 $x = B_{*,j}$ 是未知向量，$c = C_{*,j}$ 是已知向量。
   我们的任务是解这 $p$ 个线性方程组。如果所有 $p$ 个方程组都有解，那么矩阵 $B$ 就存在；只要有一个方程组无解，矩阵 $B$ 就不存在。

4. 高斯消元: 解线性方程组 $A \times x = c$ 在 GF(2) 上的标准方法是高斯消元法。

   • 构造增广矩阵 $[A | c]$。
   • 通过行变换（只允许两种：交换两行、将一行加到另一行，在 GF(2) 中加法就是异或）将左侧的 $A$ 部分化为行阶梯形式 (Row Echelon Form) 或简化行阶梯形式 (Reduced Row Echelon Form)。
   • 判断是否有解: 在消元过程中，如果出现某一行形如 $[0, 0, \dots, 0 | 1]$，则该方程组无解。
   • 求解: 如果有解，可以通过回代或直接从简化行阶梯形式读出解。如果有自由变量（对应非主元列），可以给自由变量赋任意值（例如 0）来得到一个特解。

5. 同时处理所有列: 我们可以同时处理 $B$ 的所有 $p$ 列。构造一个大的增广矩阵 $[A | C]$，其维度为 $n \times (m+p)$。

   • 对这个大矩阵的前 $m$ 列（对应 $A$）进行高斯消元，目标是将其化为行阶梯形式。所有的行变换都同时应用于整个 $n \times (m+p)$ 的行。
   • 消元后，矩阵变为 $[A’ | C’]$，其中 $A’$ 是 $A$ 的行阶梯形式。设 $A’$ 的秩（非零行的数量）为 $r$。

6. 判断解的存在性 (关键步骤):

   • 高斯消元后，如果 $A’$ 的第 $i$ 行 ($i \ge r$) 是全零行，那么对于任何一个方程组 $A \times B_{*,j} = C_{*,j}$ 要有解，对应的增广矩阵 $[A | C_{*,j}]$ 经过行变换后，得到的 $[A’ | C’_{*,j}]$ 的第 $i$ 行必须也是全零行。也就是说，$C’_{i,j}$ 必须为 0。
   • 综合起来，如果存在任何一行 $i$ ($r \le i < n$) 使得 $A’$ 的第 $i$ 行是全零行，但 $C’$ 的第 $i$ 行 不是 全零行（即存在某个 $j$ 使得 $C’_{i,j} = 1$），那么对应的至少一个方程组 $A \times B_{*,j} = C_{*,j}$ 无解，因此整个矩阵 $B$ 不存在。

7. 构造解 (如果存在):

   • 如果对于所有 $i$ ($r \le i < n$)，只要 $A’$ 的第 $i$ 行是全零行，$C’$ 的第 $i$ 行也必然是全零行，那么解就存在。
   • 我们需要找到 一个 解 $B$。我们可以通过给自由变量赋值（通常赋 0）来获得一个特解。
   • 高斯消元过程（特别是化为简化行阶梯形式，虽然本代码只化到行阶梯形式也足够）可以得到每个主元变量（对应主元列的 $B_{k,j}$）关于自由变量和 $C’$ 中对应项的表达式。
   • 一个更直接的方法是：假设高斯消元将 $A$ 化为了 $A’$，并且记录了主元列的位置。令 $pc[i]$ 为第 $i$ 个主元所在的列号（$0 \le i < r$）。化为行阶梯形式后，对于每个主元行 $i$，方程 $A’_{i,*} \times B_{*,j} = C’_{i,j}$ 可以写成：
     $$B_{pc[i], j} \oplus \sum_{k=pc[i]+1}^{m-1} A’_{i,k} B_{k,j} = C’_{i,j}$$
     (因为 $A’_{i, pc[i]} = 1$，且 $A’_{i, k’} = 0$ for $k’ < pc[i]$)
   • 为了得到一个特解，我们设置所有自由变量 $B_{k,j}$（其中 $k$ 不是任何主元列 $pc[0], \dots, pc[r-1]$）为 0。
   • 那么方程简化为 $B_{pc[i], j} = C’_{i,j}$。
   • 因此，我们可以构造解 $B$：初始化 $B$ 为全零矩阵。然后对于每个主元行 $i$ ($0 \le i < r$)，令 $k = pc[i]$ (主元列)。对于 $B$ 的所有列 $j$ ($0 \le j < p$)，设置 $B_{k, j} = C’_{i,j}$ (即增广矩阵中 a[i][m+j] 的值)。

8. 代码实现:

   • 使用 std::vector<bitset<N>> 来存储增广矩阵 $[A | C]$，其中 N 足够大 (例如 $m+p+5$)。bitset 非常适合 GF(2) 上的行操作 (异或)。
   • a[i] 代表增广矩阵的第 $i$ 行。a[i][j] (for $0 \le j < m$) 是 $A$ 部分，a[i][m+j] (for $0 \le j < p$) 是 $C$ 部分。
   • gauss 函数实现了高斯消元，将 $A$ 部分化为行阶梯形式，并返回秩 $r$。同时，pc 数组记录了每个主元行 $i$ 的主元列号 pc[i]。
   • 判断解是否存在：检查从第 $r$ 行到第 $n-1$ 行，对应的 $C’$ 部分 (a[i][m...m+p-1]) 是否全为 0。如果有任何一个 1，则 ok = false。
   • 构造解：如果 ok 为 true，创建一个 $m \times p$ 的 bitset 数组 b (初始化为 0)。遍历主元行 $i$ 从 0 到 $r-1$，找到主元列 $k = pc[i]$。将变换后的 $C’$ 对应行的 $j$ 列 (a[i][m+j]) 的值赋给 b[k][j]。
   • 输出 “Yes” 和矩阵 $B$，或者输出 “No”。

时间复杂度

• 高斯消元主要操作是在 $n \times (m+p)$ 的矩阵上进行。找到主元和进行行异或操作是主要步骤。
• 标准高斯消元复杂度约为 $O(n \cdot m \cdot \min(n, m))$。
• 使用 bitset 时，一行与另一行异或的时间复杂度是 $O(\frac{m+p}{w})$，其中 $w$ 是机器字长（通常是 64）。
• 整个高斯消元过程大致需要进行 $O(n \cdot m)$ 次（或 $O(n \cdot \min(n,m))$ 次）行异或操作。
• 总时间复杂度约为 $O(n \cdot m \cdot \frac{m+p}{w})$ 或 $O(n \cdot \min(n, m) \cdot \frac{m+p}{w})$。考虑到 $n, m, p \le 1000$，这个复杂度是可以接受的。更宽松的估计是 $O(n^2 \frac{m+p}{w})$ 或 $O(nm \frac{m+p}{w})$.

参考文献

• 高斯消元法 (Gaussian Elimination)
• 线性方程组求解 (Solving Systems of Linear Equations)
• 有限域 GF(2) 上的运算

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (虽然本题未使用)

constexpr int N = 2005; // 定义 bitset 的大小，应大于等于 m + p

int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, p; // 矩阵维度 n*m, m*p, n*p
    cin >> n >> m >> p;

    // 使用 vector<bitset> 存储增广矩阵 [A | C]
    // 大小为 n 行，N 列 (N >= m + p)
    vector<bitset<N>> a(n);
    // 读入矩阵 A (前 m 列)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            if (x) a[i][j] = 1; // 如果输入是 1，bitset 对应位设为 1
        }
    }

    // 读入矩阵 C (接在 A 后面的 p 列，即 m 到 m+p-1 列)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < p; j++) {
            int x;
            cin >> x;
            if (x) a[i][m + j] = 1; // 设置增广矩阵 C 部分
        }
    }

    // 高斯消元函数 (lambda 表达式)
    // 参数: a - 增广矩阵 (引用传递), n - 行数, m - A 的列数, pc - 存储主元列位置 (引用传递)
    // 返回值: 矩阵 A 的秩 r
    auto gauss = [&](vector<bitset<N>>& a, int n, int m, vector<int>& pc) {
        int r = 0; // 当前处理到的主元行行号 (秩)
        pc.assign(n, -1); // 初始化主元列数组 pc，-1 表示该行没有主元
        // 遍历 A 的列 c (0 到 m-1)，寻找主元
        for (int c = 0; c < m && r < n; c++) {
            int pr = r; // 从当前行 r 开始向下找主元行
            while (pr < n && !a[pr][c]) pr++; // 找到第一个在 c 列为 1 的行 pr
            if (pr == n) continue; // 如果 c 列在 r 行及以下全为 0，跳到下一列

            swap(a[r], a[pr]); // 将找到的主元行 pr 与当前行 r 交换

            // 将 r 行的主元列记录下来
            pc[r] = c; 

            // 消元：用主元行 r 去消掉其他行在 c 列的 1
            for (int i = 0; i < n; i++) {
                // 如果 i 行不是主元行 r，并且 i 行在 c 列也为 1
                if (i != r && a[i][c]) {
                    a[i] ^= a[r]; // 将主元行 r 异或到 i 行 (a[i] = a[i] XOR a[r])
                }
            }
            r++; // 处理完一个主元，秩增加 1
        }
        return r; // 返回最终的秩
    };

    vector<int> pc; // 存储主元列的位置
    int r = gauss(a, n, m, pc); // 执行高斯消元，得到秩 r 和主元列 pc

    bool ok = true; // 标记是否存在解
    // 检查是否存在无解情况
    // 遍历消元后矩阵的非主元行 (从 r 到 n-1)
    for (int i = r; i < n; i++) {
        // 检查这些行的 C' 部分 (列 m 到 m+p-1) 是否全为 0
        for (int j = m; j < m + p; j++) {
            // 如果发现 C' 部分有 1，说明方程组无解
            if (a[i][j]) {
                ok = false;
                break;
            }
        }
        if (!ok) break; // 如果已发现无解，提前退出外层循环
    }

    // 根据 ok 的值输出结果
    if (!ok) {
        cout << "No\n"; // 无解
    } else {
        cout << "Yes\n"; // 有解
        // 构造一个解 B
        vector<bitset<N>> b(m); // 创建 m 行 N 列的 bitset 数组 (实际只需要 p 列)
        // 遍历主元行 i (0 到 r-1)
        for (int i = 0; i < r; i++) {
            int k = pc[i]; // 获取第 i 行的主元列 k
            if (k != -1) { // 确保主元存在 (虽然理论上 gauss 后 0 到 r-1 行都有主元)
                // 对于 B 的每一列 j (0 到 p-1)
                for (int j = 0; j < p; j++) {
                    // B[k][j] 的值由消元后增广矩阵的 a[i][m+j] 决定
                    b[k][j] = a[i][m + j]; 
                }
            }
        }
        // 输出构造的矩阵 B (m 行 p 列)
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < p; j++) {
                cout << b[i][j] << " \n"[j == p - 1]; // 输出 0 或 1，并在行末输出换行
            }
        }
    }

    return 0; // 程序正常结束
}