题目翻译

E. 构造矩阵
给定一个偶数 $n$ 和一个整数 $k$，构造一个 $n \times n$ 的 $0/1$ 矩阵，满足：

1. 矩阵中所有数的和恰好为 $k$；
2. 每一行的 XOR 值相同；
3. 每一列的 XOR 值相同。

若可能，输出 Yes 及矩阵；否则输出 No。

---

一、基本性质分析

1.1 XOR 与奇偶性

对于 $0/1$ 序列，XOR 等于 $1$ 当且仅当 $1$ 的个数为奇数。
因此，“行 XOR 相同” 等价于 每行 $1$ 的个数的奇偶性相同。列同理。

设每行有 $r$ 个 $1$（$r$ 为整数，奇偶性固定），则总 $1$ 数 $k = n \cdot r$。
因为 $n$ 是偶数，所以： [ k \equiv 0 \pmod{2} ] 结论 1：$k$ 必须是偶数。若 $k$ 为奇数，直接输出 No。

1.2 特殊情况 $k = 2$ 或 $k = n^2 - 2$

• 若 $k = 2$，只有两个 $1$。
  由于每行 XOR 相等，这两个 $1$ 必须在同一行（否则两行 XOR 不同）。
  但这样就会有两列各有一个 $1$，其余列全 $0$，列 XOR 不相等。
  当 $n=2$ 时，可以构造： [ \begin{bmatrix}1 & 1 \ 0 & 0\end{bmatrix} ] 行 XOR：$0,0$；列 XOR：$1,1$，满足要求。
  对于 $n>2$，无解。

• 若 $k = n^2 - 2$，相当于全 $1$ 矩阵去掉两个 $1$。
  对称分析可知，也只有 $n=2$ 时可行（此时 $k=2$，同上）。

结论 2：若 $n > 2$ 且 $k = 2$ 或 $k = n^2 - 2$，则无解。

---

二、一般情况的构造

当 $k$ 为偶数且不满足上述特殊情况时，一定有解。
我们按 $k \bmod 4$ 分类构造。

2.1 情况一：$k \equiv 0 \pmod{4}$

令 $k = 4m$，$m$ 为非负整数。

构造方法：
将 $n \times n$ 矩阵划分为 $\frac{n}{2} \times \frac{n}{2}$ 个互不重叠的 $2 \times 2$ 子矩阵。
每个 $2 \times 2$ 子矩阵全填 $1$ 会贡献 $4$ 个 $1$，且该子矩阵的每行有 $2$ 个 $1$（偶数），每列有 $2$ 个 $1$（偶数），因此不会破坏整体行/列 XOR 的相等性（保持为 $0$）。

我们只需选择 $m$ 个这样的子矩阵（例如按行优先顺序取前 $m$ 个），将它们全部填 $1$，其余位置填 $0$。

验证：

• 总 $1$ 数 $= 4m = k$。
• 每行包含若干个完整的 $2 \times 2$ 块，每个块在该行贡献 $2$ 个 $1$，因此每行 $1$ 的个数为偶数 → 行 XOR 均为 $0$。
• 同理每列 XOR 也为 $0$。

2.2 情况二：$k \equiv 2 \pmod{4}$

此时 $k = 4m + 2$，且 $k \ge 6$（因为 $k=2$ 且 $n>2$ 已排除）。

第一步：放置一个 $3 \times 3$ 的“种子”模式

在左上角 $3 \times 3$ 子矩阵中填入以下 $6$ 个 $1$： [ \begin{bmatrix} 1 & 1 & 0 \ 1 & 0 & 1 \ 0 & 1 & 1 \end{bmatrix} ] 即位置：$(1,1), (1,2), (2,1), (2,3), (3,2), (3,3)$。

检查：每行每列均有 $2$ 个 $1$（偶数），因此行/列 XOR 均为 $0$。

第二步：填充剩余的 $k-6$ 个 $1$

因为 $k \equiv 2 \pmod{4}$，所以 $k-6 \equiv 0 \pmod{4}$，设 $k-6 = 4t$。

固定前 $4$ 行 $4$ 列，其中前 $3$ 行 $3$ 列已填好种子模式，第 $4$ 行和第 $4$ 列暂时全 $0$。
剩下的部分是 $(n-4) \times (n-4)$ 的子矩阵，其行数和列数均为偶数（因为 $n$ 偶，$n-4$ 偶）。
我们可以将这个子矩阵划分为 $\frac{n-4}{2} \times \frac{n-4}{2}$ 个 $2 \times 2$ 块，每个块可以独立地全填 $1$。

我们只需从中选择 $t$ 个 $2 \times 2$ 块全填 $1$，其余全 $0$。

第三步：处理边界情况 $k = n^2 - 6$

当 $k = n^2 - 6$ 时，$k-6 = n^2 - 12$，需要 $t = \frac{n^2-12}{4}$ 个 $2 \times 2$ 全 $1$ 块。
但 $(n-4) \times (n-4)$ 区域最多只能容纳 $\frac{(n-4)^2}{4}$ 个 $2 \times 2$ 块，当 $n>4$ 时这个数小于 $t$。

因此需要特殊处理：在 $4 \times 4$ 的左上角额外再填 $4$ 个 $1$，位置为 $(1,3), (1,4), (4,3), (4,4)$。

此时 $4 \times 4$ 区域变为： [ \begin{bmatrix} 1 & 1 & 1 & 1 \ 1 & 0 & 1 & 0 \ 0 & 1 & 1 & 0 \ 0 & 0 & 1 & 1 \end{bmatrix} ] 每行每列均为偶数个 $1$，共 $10$ 个 $1$。
此时 $k-10 = n^2 - 16$，恰好等于 $(n-4) \times (n-4)$ 区域全部填满 $2 \times 2$ 全 $1$ 块的总 $1$ 数。

---

三、算法步骤总结

对于每个测试用例：

1. 若 $k$ 为奇数 → 输出 No。
2. 若 $n > 2$ 且 ($k = 2$ 或 $k = n^2 - 2$) → 输出 No。
3. 否则：
   • 初始化全 $0$ 矩阵。
   • 若 $k \equiv 0 \pmod{4}$： 令 $m = k/4$，按行优先顺序取 $m$ 个不重叠的 $2 \times 2$ 子矩阵全填 $1$。
   • 若 $k \equiv 2 \pmod{4}$： 在 $(1,1),(1,2),(2,1),(2,3),(3,2),(3,3)$ 填 $1$。 若 $k = n^2 - 6$，额外在 $(1,3),(1,4),(4,3),(4,4)$ 填 $1$。 令 $t = (k-6)/4$（若 $k = n^2 - 6$ 则 $t = (n^2-16)/4$），从第 $4$ 行第 $4$ 列开始填充 $t$ 个 $2 \times 2$ 全 $1$ 块。
   • 输出 Yes 和矩阵。

---

四、参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, k;
        cin >> n >> k;
        
        // 无解判断
        if (k % 2 == 1) {
            cout << "No\n";
            continue;
        }
        if (n > 2 && (k == 2 || k == n * n - 2)) {
            cout << "No\n";
            continue;
        }
        
        // 有解，开始构造
        cout << "Yes\n";
        vector<vector<int>> a(n, vector<int>(n, 0));
        
        if (k % 4 == 0) {
            // k ≡ 0 (mod 4)：填充 2x2 全1块
            int cnt = k / 4;
            for (int i = 0; i + 1 < n && cnt > 0; i += 2) {
                for (int j = 0; j + 1 < n && cnt > 0; j += 2) {
                    a[i][j] = a[i][j+1] = a[i+1][j] = a[i+1][j+1] = 1;
                    cnt--;
                }
            }
        } else {
            // k ≡ 2 (mod 4)：种子模式
            a[0][0] = a[0][1] = 1;
            a[1][0] = a[1][2] = 1;
            a[2][1] = a[2][2] = 1;
            
            // 处理 k = n^2 - 6 的特殊情况
            if (k == n * n - 6) {
                a[0][2] = a[0][3] = 1;
                a[3][2] = a[3][3] = 1;
            }
            
            // 填充剩余的 2x2 全1块
            int remaining = k - 6;
            if (k == n * n - 6) remaining -= 4;
            int cnt = remaining / 4;
            
            for (int i = 4; i + 1 < n && cnt > 0; i += 2) {
                for (int j = 4; j + 1 < n && cnt > 0; j += 2) {
                    a[i][j] = a[i][j+1] = a[i+1][j] = a[i+1][j+1] = 1;
                    cnt--;
                }
            }
        }
        
        // 输出矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << a[i][j] << " \n"[j == n-1];
            }
        }
    }
    
    return 0;
}

---

五、复杂度分析

• 时间复杂度：$O(n^2)$ 每个测试用例
• 空间复杂度：$O(n^2)$
• 所有测试用例的 $n$ 之和不超过 $2000$，完全可行

---

六、示例验证

输入	输出
$4\ 0$	Yes + 全 $0$ 矩阵
$6\ 6$	Yes + 种子模式扩展到 $6\times6$
$6\ 5$	No
$4\ 2$
$6\ 36$	Yes + 全 $1$ 矩阵