题解：特殊的矩阵乘法

问题分析

我们有两个 $n \times n$ 的 0-1 矩阵 $A$ 和 $B$，在 $\mathbb{F}_2$（模 2）下运算。

要求对于所有 $i,j$：

$$(AB)_{ij} \equiv A_{ij} \cdot B_{ij} \pmod 2$$

其中左边是标准矩阵乘法：

$$(AB)_{ij} = \sum_{t=1}^n A_{it} B_{tj} \pmod 2$$

右边是逐元素乘积。

并且 $B$ 中恰好有 $k$ 个 1。

---

关键推导

将条件重写：

$$\sum_{t=1}^n A_{it} B_{tj} \equiv A_{ij} B_{ij} \pmod 2 $$

移项：

$$\sum_{t=1}^n A_{it} B_{tj} - A_{ij} B_{ij} \equiv 0 \pmod 2 $$

注意在 $\mathbb{F}_2$ 中减法等于加法：

$$\sum_{t=1}^n A_{it} B_{tj} + A_{ij} B_{ij} \equiv 0 \pmod 2 $$

但更清晰的写法是：

$$\sum_{t \neq j} A_{it} B_{tj} + A_{ij} B_{ij} + A_{ij} B_{ij} \equiv \sum_{t \neq j} A_{it} B_{tj} \equiv 0 \pmod 2 $$

因为 $A_{ij} B_{ij} + A_{ij} B_{ij} = 2A_{ij} B_{ij} \equiv 0 \pmod 2$。

---

得到核心条件

对于所有 $i,j$：

$$\sum_{t \neq j} A_{it} B_{tj} \equiv 0 \pmod 2$$

---

分析结构

固定 $j$，考虑第 $j$ 列 $B_{:,j}$。条件变为对于所有 $i$：

$$\sum_{t \neq j} A_{it} B_{tj} \equiv 0 \pmod 2$$

这是一个线性方程组，有 $n$ 个方程，$n-1$ 个未知数 $B_{tj}$（$t \neq j$）。

由于 $A$ 是随机 0-1 矩阵，在 $\mathbb{F}_2$ 上几乎总是满秩或接近满秩。对于 $n=100$，$n$ 个方程约束 $n-1$ 个变量，通常只有零解。

因此对于每个 $j$，必须有：

$$B_{tj} = 0 \quad \text{对于所有 } t \neq j$$

---

B 必须是对角矩阵

所以 $B$ 的形式必须是：

$$B_{ij} = \begin{cases} b_i & \text{if } i = j \\ 0 & \text{if } i \neq j \end{cases} $$

其中 $b_i \in \{0,1\}$。

---

验证对角矩阵满足条件

如果 $B$ 是对角矩阵，那么：

• 左边：$(AB)_{ij} = \sum_{t=1}^n A_{it} B_{tj} = A_{ij} B_{jj}$（因为 $B_{tj} = 0$ 当 $t \neq j$）
• 右边：$A_{ij} B_{ij} = A_{ij} B_{jj}$（因为 $B_{ij} = 0$ 当 $i \neq j$，且当 $i = j$ 时 $B_{ij} = B_{jj}$）

所以条件自动满足！

---

问题简化

问题转化为：构造对角矩阵 $B$，使得对角线元素 $b_1, \dots, b_n \in \{0,1\}$，且 $\sum_{i=1}^n b_i = k$。

---

解的存在性

• 如果 $0 \leq k \leq n$，存在解（选择任意 $k$ 个位置为 1，其余为 0）
• 如果 $k > n$，无解（因为对角矩阵最多有 $n$ 个 1）

---

算法步骤

1. 如果 $k > n$，输出 -1
2. 否则：
   • 创建 $n \times n$ 的全零矩阵
   • 选择任意 $k$ 个对角线位置设为 1
   • 输出矩阵

---

时间复杂度

$O(n^2)$，在 $n=100$ 时非常快。

---

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<vector<int>> A(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> A[i][j];
        }
    }
    
    if (k > n) {
        cout << -1 << endl;
        return 0;
    }
    
    vector<vector<int>> B(n, vector<int>(n, 0));
    
    // 设置前k个对角线元素为1
    for (int i = 0; i < k; i++) {
        B[i][i] = 1;
    }
    
    cout << 1 << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << B[i][j];
            if (j < n - 1) cout << " ";
        }
        cout << endl;
    }
    
    return 0;
}

---

样例验证

样例输入：

3 3
1 0 0
0 1 0
0 0 1

运行：

• $k=3 \leq n=3$，有解
• 设置 $B_{11}=1, B_{22}=1, B_{33}=1$
• 输出对角矩阵

与样例输出一致。

---

总结

本题的关键洞察是：

1. 通过代数推导发现 $B$ 必须是对角矩阵
2. 对角矩阵自动满足题目条件
3. 问题简化为选择 $k$ 个对角线位置设为 1
4. 解存在的充要条件是 $0 \leq k \leq n$

这是一个基于线性代数推导的构造题，核心在于发现矩阵 $B$ 的特殊结构。