The Very Beautiful Blanket 题解

· · 题解

题意

你需要构造一个 n \times m 的正整数矩阵，使得任意 4 \times 4 大小的子矩阵中，左上角四个点的异或和和右下角四个相等，右上角四个和左下角四个相等。

a b c d
e f g h
i j k l 
m n o p

即在上图中，a \oplus b \oplus e \oplus f = k \oplus l \oplus o \oplus p 且 c \oplus d \oplus g \oplus h = i \oplus j \oplus m \oplus n。

此外，你要使矩阵中不同的数字尽可能多，先输出不同数字的数量，再输出这个矩阵。

题解

构造题，我不晓得咋个讲，先说答案。

对于数字总量，直接输出 n \times m。

对于矩阵的第 i 行第 j 列，输出 (i \times 2^9) \oplus j。

code

#include<cstdio>
int t,n,m;
signed main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        printf("%d\n",n*m);
        for(int i=1;i<=n;i++,puts(""))
            for(int j=1;j<=m;j++)
                printf("%d ",(i<<9)^(j));
    }
}
//其实我写这个题解就是为了炫耀我这个巨短的代码的

正确性证明

假设有以下一个子矩阵。

a b
c d

令 a 在第 i 行 j 列，则：

a = (i \times 2^9) \oplus j b = (i \times 2^9) \oplus (j + 1) c = ((i + 1) \times 2^9) \oplus j d = ((i + 1) \times 2^9) \oplus (j + 1)

故

a \oplus b \oplus c \oplus d = ((i \times 2^9) \oplus (i \times 2^9)) \oplus (((i + 1) \times 2^9) \oplus ((i + 1) \times 2^9)) \oplus (j \oplus j) \oplus ((j + 1) \oplus (j + 1)) = 0 \oplus 0 \oplus 0 \oplus 0 = 0

显然所有 2 \times 2 的子矩阵异或和都为 0，满足条件。

其实这反过来问就是为什么 i 要乘以 2^9。

由于 m,n \leq 200，故 2^9=512 \ge m。

那么将 i 乘上这个数，不仅不会使局部二进制位变化，还使其不会影响 j 管辖的后 8 位，不会出现 i,j 两部分互相影响导致数字重复的情况，此时异或等价于加法。

所以其实不一定要乘 2^9，也不一定要 i 来乘，只要保证不爆 long long，也不影响另一部分、等价于加法就行了。