CFR-857解题报告

比赛传送门

A. The Very Beautiful Blanket

题意：构造一个 \(n\times m\) 的矩阵，使得任意 \(4\times 4\) 的子矩阵中，左上 \(2\times 2\) 与右下 \(2\times 2\) 的矩阵的异或和，等于右上 \(2\times 2\) 与左下 \(2\times 2\) 的矩阵的异或和。

这个限制看起来非常难以处理，但非常宽松，于是可以想到人为构造一种更强的限制，使得新限制是原限制的充分条件，且较容易构造。

一种容易想到的方式为，只要让任意 \(2\times 2\) 的子矩阵的异或和均为 \(0\)，显然可满足要求。以下为两种较简单的构造：

随机

因为任意 \(2\times 2\) 的子矩阵异或和为 \(0\)，则只要有三个确定了，第四个唯一确定。于是可以发现，第一行和第一列确定后，就能唯一确定一个 \(n\times m\) 的矩阵（递推即可）。第一行和第一列可以随机，正确率足够通过本题。如果放不下心可以最后加一个判断，不合法则重新随机。

By cxm1024

long long a[210][210];
void Solve(int test) {
	int n, m;
	cin >> n >> m;
	while (1) {
		for (int i = 1; i <= n; i++)
			a[i][1] = abs((long long)(1ull * rand() * rand() * rand()));
		for (int i = 1; i <= m; i++)
			a[1][i] = abs((long long)(1ull * rand() * rand() * rand()));
		for (int i = 2; i <= n; i++)
			for (int j = 2; j <= m; j++)
				a[i][j] = a[i - 1][j - 1] ^ a[i - 1][j] ^ a[i][j - 1];
		// set<int> s;
		// for (int i = 1; i <= n; i++)
		// 	for (int j = 1; j <= m; j++)
		// 		s.insert(a[i][j]);
		// if (s.size() != n * m) continue;
		// 注释部分为判断合法性，不加也可通过
		cout << n * m << endl;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++)
				cout << a[i][j] << " ";
			cout << endl;
		}
		break;
	}
}

人类智慧

第二种为直接构造，思维难度相对较高。对于 \(2\times 2\) 的子矩阵中的元素，考虑在二进制位上分段处理，分为前后两段，前面的段每一行相同，后面的段每一列相同。这样，同行的两个元素异或会把前面的段抵消，同列的两个元素异或会把后面的段抵消，保证异或和为 \(0\)。

实现上，直接令 \(a_{i,j}=i\times 2^k+j\)，其中 \(k\) 是足以区分两段的常数（本题中取 \(8\) 以上即可）。

By jiangly

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    std::cout << n * m << "\n";
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cout << (i << 10) + j << " \n"[j == m - 1];
        }
    }
}

其他做法

除此之外，还有很多种其他做法，如对样例找规律、递归分治加位等，但本质上都是要构造使得任意 \(2\times 2\) 的矩阵异或和为 \(0\)，这里不再赘述。