P17863 「GLR-R5」中秋 / plenilune

[被出题人杀掉的某个题目背景](https://www.luogu.com.cn/paste/v8886pd4)  

  我们把网格的八个方向按如下顺序（从 $(0,1)$ 开始顺时针旋转）从 $0$ 到 $7$ 编号： $$ 0:(0,1),1:(1,1),2:(1,0),3:(1,-1),4:(0,-1),5:(-1,-1),6:(-1,0),7:(-1,1) $$   一个方向集合 $S$ 是 $\{0,1,\dots,7\}$ 的子集，用整数 $c\in[0,255]$ 编码：$c$ 的二进制第 $k$ 位（$0\le k

输入的第一行包含两个整数 $T,t$，分别表示测试数据组数和子任务编号。 接下来 $T$ 行，每行包含三个整数 $n,m,c$，分别表示网格的行数、列数和询问参数，满足 $0\le c\le 256$。 当 $c=256$ 时，需要判断所有 $256$ 个方向集合；当 $0\le c

对于每组测试数据，按以下格式输出。 若 $c=256$，输出一行一个长度为 $256$ 的字符串，仅由字符 `0`、`1` 组成。从左到右第 $k$ 个字符（$1\le k\le 256$）表示编码为 $k-1$ 的方向集合是否存在符合要求的行走方案：`1` 表示存在，`0` 表示不存在。 若 $c\ne 256$，第一行输出一个整数 $r\in\{0,1\}$，表示编码为 $c$ 的方向集合是否存在符合要求的行走方案。若不存在，输出 `0`，该组测试数据的输出结束；若存在，输出 `1`，接下来输出 $n$ 行，每行包含 $m$ 个整数，表示一个合法的访问顺序，整数之间用单个空格分隔。 对于输出的矩阵，第 $x$ 行第 $y$ 列的整数表示到达格子 $(x,y)$ 的步数。这些整数必须恰好为 $1,2,\dots,n\times m$ 的一个排列，其中格子 $(1,1)$ 处为 $1$，格子 $(n,m)$ 处为 $n\times m$。相邻两步所在格子的位置差必须是 $S$ 中某个方向对应的方向向量。

**【数据范围】** 记 $k=\operatorname{popcount}(c)$，即 $c$ 的二进制表示中 $1$ 的个数。记 $N$ 为单个测试点内所有需要输出构造矩阵的测试数据的 $nm$ 之和。参数 $c=256$ 的测试数据不需要输出矩阵，不计入 $N$。 对于所有测试数据，均有： - $1\le T\le 10^4$，$0\le t\le 9$； - $5\le n,m\le 10^9$，$N\le 10^6$； - $0\le c\le 256$。 **本题采用捆绑测试。** 若无特殊说明，时间限制为 $1$ 秒。各子任务的分值及额外约束如下表所示。 ::cute-table{tuack} | 子任务编号 | $c$ | $k$ | 特殊性质 | 分值 | | :---: | :---: | :---: | :---: | :---: | | $1$ | / | / | A | $2$ | | $2$ | $=73$ | $=3$ | 无 | $8$ | | $3$ | $\ne 256$ | $\le 3$ | ^ | $10$ | | $4$ | $=75$ | $=4$ | ^ | ^ | | $5$ | $=90$ | ^ | ^ | $20$ | | $6$ | / | ^ | ^ | ^ | | $7$ | $=186$ | $=5$ | ^ | $10$ | | $8$ | / | $\ge 5$ | ^ | ^ | | $9$ | $=256$ | / | B | $10$ | 特殊性质 A：保证 $5 \le n,m \le 7$。 特殊性质 B：此个子任务满足 $T \le 2000$，时间限制为 3s。 题目附件中提供了一个手动构造的可视化工具。