P8167 [eJOI 2021] XCopy

给定正整数 $N,M$。 请构造一个 $N \times M$ 的只包含非负整数的矩阵，使得每个元素互不相同且相邻（上下左右）元素在二进制下只有一位不同，同时保证矩阵的最大元素最小。

一行两个正整数 $N,M$。

一个 $N \times M$ 的只包含非负整数的矩阵。**Special Judge 对输出格式要求非常严格，每行行末不能有空格等多余字符。**

#### 评分规则 本题采用部分分计分，分数取决于输出答案和正确答案的大小。其中「答案」指的是矩阵中的最大元素。 设 $S$ 为该测试点的总分，$O$ 为正确答案。那么当 $G$ 为输出答案时，得分为： $$S \times \max(1-\sqrt{\dfrac{\frac{G}{O}-1}{3}},0)$$ 由于洛谷评分机制，每个测试点的实际得分为上式下取整的结果，即 $\lfloor S \times \max(1-\sqrt{\dfrac{\frac{G}{O}-1}{3}},0) \rfloor$。例如，当 $S=7,G=15,O=10$ 时，按上式得分约为 $4.14$ ，但在洛谷上得分为 $4$。 如果输出矩阵不满足要求（即元素互不相同且相邻元素在二进制下只有一位不同），那么该测试点计 $0$ 分。 注意，由于 Special Judge 对于格式要求较高，请在输出答案时**不要在每行末尾添加多余空格**，否则对应测试点会被计为 $0$ 分。另外，请不要输出超出 $[0,2^{63})$ 范围（long long）的整数，否则会被判为格式错误，计 $0$ 分。 #### 样例解释 样例矩阵如下： |$0101_2=5_{10}$|$0100_2=4_{10}$|$0110_2=6_{10}$| | :----------: | :----------: | :----------: | |$0001_2=1_{10}$|$0000_2=0_{10}$|$0010_2=2_{10}$| |$1001_2=9_{10}$|$1000_2=8_{10}$|$1010_2=10_{10}$| 通过观察不难发现，每两个相邻元素在二进制下都只有一位不同。这种做法的答案为 $10$（即最大元素），是所有做法中最小的。当然，其它的最大元素为 $10$ 的矩阵也是符合题意的（例如将输入矩阵进行翻转操作等）。 一种可以获得部分分的做法是： |$0110_2$|$0111_2$|$0101_2$| | :----------: | :----------: | :----------: | |$1110_2$|$1111_2$|$1101_2$| |$1010_2$|$1011_2$|$1001_2$| 该矩阵的最大元素为 $15$。根据评分规则，这种做法在下取整前可以获得对应测试点 $\max(1-\sqrt{\dfrac{\frac{15}{10}-1}{3}},0)=1-\dfrac{\sqrt{6}}{6} \approx 59\%$ 的分数。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（7 pts）：$N=1$。 - Subtask 2（9 pts）：$N,M$ 是 $2$ 的整数幂。 - Subtask 3（14 pts）：$N$ 是 $2$ 的整数幂。 - Subtask 4（70 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le N,M \le 2000$。 #### 说明 本题译自 [eJOI2021](https://sepi.ro/ejoi/2021) Day 1 C XCopy。欢迎通过私信或发帖的方式对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/cbrnaqp0) 进行 hack。