CF1917E 题解

sunkuangzheng · 2023-12-25 14:23:55 · 题解

只需要用 2 \times 2 的 1 矩阵一直填即可，填一个 2 \times 2 的矩阵显然不会影响任何一行和任何一列的异或和。

6 \le k \le n^2-10 且 k \bmod 4 = 2

考虑在左上角构造一个这样的图案：

它会用去 6 个 1，填完后 k \bmod 4 = 0，在剩余位置继续填 2 \times 2 矩阵即可。

k= n^2-6

把除了左上角以外填满，左上角在刚才的基础上需要多填四个位置。

这样填的依据是，要保证每一行每一列的异或和不变。

k=2 或 k=n^2-2

这两种情况本质等价，我们只考虑 k=2。

如果两个位置填在同一行，那么列的异或和必定不同，反之亦然。因此，k=2 时只有 n=2 有解，其余情况无解。

按照上面的分类模拟即可。

/**
 *    author: sunkuangzheng
 *    created: 25.12.2023 10:40:05
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
debug_helper deg;
#endif
using ll = long long;
const int N = 1e3+5;
using namespace std;
int T,n,k,a[N][N];
void los(){
    cin >> n >> k;
    for(int i = 1;i <= n;i ++) for(int j = 1;j <= n;j ++) a[i][j] = 0;
    if(k & 1) return cout << "No\n",void();
    if(n == 2){
        if(!k) cout << "Yes\n0 0\n0 0\n";
        if(k == 2) cout << "Yes\n1 0\n0 1\n";
        if(k == 4) cout << "Yes\n1 1\n1 1\n"; 
        return ;
    }if(k == n * n - 2 || k == 2) return cout << "No\n",void();
    for(int i = 1;i <= n;i += 2) for(int j = 1;j <= n;j += 2)
        if(k >= 8 && (i > 4 || j > 4)) a[i][j] = a[i+1][j] = a[i][j+1] = a[i+1][j+1] = 1,k -= 4;
    if(k % 4) a[1][1] = a[1][2] = a[2][1] = a[2][3] = a[3][2] = a[3][3] = 1,k -= 6;
    else for(int i = 1;i <= 4;i += 2) for(int j = 1;j <= 4;j += 2)
        if(k >= 4) a[i][j] = a[i+1][j] = a[i][j+1] = a[i+1][j+1] = 1,k -= 4;
    if(k) assert(k == 4),a[3][1] = a[4][1] = a[3][4] = a[4][4] = 1,k -= 4;
    assert(k == 0);
    cout << "Yes\n";
    for(int i = 1;i <= n;i ++,cout << "\n") for(int j = 1;j <= n;j ++) cout << a[i][j] << " ";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}