CF1917E Construct Matrix TJ

· · 题解

E_Construct_Matrix题解

题面

Luogu

Codeforces

思路

考虑分块，把大矩阵分成多个分块矩阵。

我们容易构造出： \begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix}，\begin{pmatrix} 1 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 1 \end{pmatrix} 每行每列的异或值都是 0 且贡献分别是 4 和 6。

考虑到 n 是偶数且 2 \times 2 的小矩阵能贡献 4。我们有如下讨论：

当 4 \mid k，我们能构造出一个大矩阵能分块出 \frac{k}{4} 个 2 \times 2 的 \begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix} 矩阵，与 \frac{n^2 - k}{4} 个 2 \times 2 的 \begin{pmatrix} 0 & 0\\ 0 & 0 \end{pmatrix} 矩阵。

例如 n = 4, k = 12 时：

1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{pmatrix}

当 4 \nmid k 时，我们考虑使用 \begin{pmatrix} 1 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 1 \end{pmatrix} 贡献。

举例 n = 8 时，我们若分块出一个上文的 3 \times 3 的矩阵，则剩下区域考虑 1 最多可能长什么样。

若构造：

1 & 1 & 0 & 1 & 1 & 1 & 1 & 0\\ 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}

但似乎不优，可以更充分地使用空间。

若构造：

1 & 1 & 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{pmatrix}

我们分块出左上角 4 \times 4 的分块矩阵去贡献 6。既然动用了 4 \times 4 的矩阵，我们能否构造贡献更多的一种分块矩阵呢？

1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 1 \end{pmatrix}$ 或 $\begin{pmatrix} 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 1\\ 1 & 1 & 1 & 1 \end{pmatrix}

构造了贡献 10 的分块矩阵。

至此，包括 4 \mid k 的情况，不考虑不等关系，我们利用贡献 4 和 6 的矩阵已经可以构造出：k = 4i 或 k = 4i + 6 的情况，其中 i 为上文 2 \times 2 的分块矩阵个数。

若使用贡献 6 的分块矩阵时 k = 4i + 6 = 4 (i + 1) + 2，考虑到 0 \le i \le \frac{n ^ 2 - 16}{4}，也就是 k 的最小范围为 k \ge 6，k 的最大范围 k \le n ^ 2 - 10，我们再把贡献 6 的分块矩阵替换为使用贡献 10 的分块矩阵即可把这个 k 的最大范围变为 k \le n^2 - 6。

至此，我们实际已构造出 2 | k，0 \le k \le n 且 k \neq 2 \neq n ^ 2 - 2，的所有 k 的情况。

剩下的情况是否无解呢？

事实上，除了特例 n = 2, k = 2 时有：\begin{pmatrix} 1 & 0\\ 0 & 1\end{pmatrix}，剩下的 k = 2 或 n ^ 2 - 2 时都无解。

证明：

我们填写一个 $1$ 之后，有 $1$ 行**和** $1$ 列的异或值为 $1$，$n - 1 \ge 3$ 行**和** $n - 1 \ge 3$ 列的异或值为 $0$。 我们发现第二个 $1$ 无论填哪里都至少有 $1$ 列**或** $1$ 行的异或值为 $1$，至少有 $n - 2 \ge 2$ 行**或** $n - 2 \ge 2$ 列的异或值为 $0$。 不符合要求。 证毕。 接下来证明 $2 \nmid k$ 时一定无解。 有： $n \ge 2, 2 \nmid k, 2 \mid n

若：k 为奇数有解。

设 1 的个数为偶数的行数（即这一行的异或值为 0）为 x，设 1 的个数为奇数的行数（即这一行的异或值为 1）为 y。

因为题设，则有 2 \nmid y，且 y \ge 1。

又因为每一行的异或值相同。

所以 x = 0, y = n 或 x = n, y = 0。

又 2 \mid n

所以 y 的奇偶性矛盾。

所以此题中 2 \nmid k 时一定无解。

至此，我们讨论出了所有情况。

CODE

#include <bits/stdc++.h>
#define int long long

using namespace std;
using ll = long long;
const int _ = 2e3 + 7;

// data:
bool c[_][_];
// function:

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        memset(c, 0, sizeof c);
        int n, k;
        cin >> n >> k;
        if (k & 1) {
            cout << "No\n";
        } else {

            if (k % 4 == 0) {
                cout << "Yes\n";
                for (int i = 1; i <= n / 2; i++) {
                    for (int j = 1; j <= n / 2; j++) {
                        if (k > 0) {
                            c[2 * i][2 * j] = c[2 * i][2 * j - 1] = c[2 * i - 1][2 * j] = c[2 * i - 1][2 * j - 1] = 1;
                            k -= 4;
                        } else {
                            break;
                        }
                    }
                }
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        cout << c[i][j] << ' ';
                    }
                    cout << '\n';
                }
            } else {
                if (n == 2) {
                    cout << "Yes\n";
                    cout << "1 0\n0 1\n";
                    continue;
                }
                if (k == 2 || k == n * n - 2) {
                    cout << "No\n";
                    continue;
                }
                cout << "Yes\n";

                for (int i = 1; i <= n / 2; i++) {
                    for (int j = 1; j <= n / 2; j++) {
                        if ((i == 1 && j == 1) || (i == 1 && j == 2) || (i == 2 && j == 1) || (i == 2 && j == 2)) continue;

                        if (k > 0) {
                            if (k == 6 || k == 10) break;
                            c[2 * i][2 * j] = c[2 * i][2 * j - 1] = c[2 * i - 1][2 * j] = c[2 * i - 1][2 * j - 1] = 1;
                            k -= 4;
                        } else {
                            break;
                        }
                    }
                }
                c[1][1] = c[1][2] = c[2][1] = c[2][3] = c[3][2] = c[3][3] = 1; // if(k == 6). k must be 6 or 10
                if (k == 10)
                    c[3][1] = c[4][1] = c[3][4] = c[4][4] = 1;
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        cout << c[i][j] << ' ';
                    }
                    cout << '\n';
                }
            }
        }
    }
    return 0;
}
// submit by Acerkaio.