题目理解

经典的二进制格雷码是一个长度为 $2^n$ 的序列，每个元素是一个 $n$ 位二进制数，相邻两个数的二进制表示仅有一位不同。

超级格雷码将这个概念推广到 $B$ 进制：要求生成一个长度为 $B^n$ 的序列，每个元素是一个 $n$ 位 $B$ 进制数，同样要求相邻两个数的 $B$ 进制表示仅有一位不同。

---

关键观察

1. 问题本质

这是一个构造性组合问题，需要找到一种系统的生成方法，而不是搜索所有可能的排列。由于 $B^n$ 最大可达 $65535$，必须使用高效的构造算法。

2. 对称性与递归结构

格雷码通常具有递归构造的性质：

• 对于 $n$ 位格雷码，可以通过 $n-1$ 位格雷码反射对称地构造
• 这种构造方法天然保证了相邻码字仅有一位不同

---

算法设计

1. 递归构造思路

基例：$n=1$ 时，超级格雷码就是数字 $0, 1, \ldots, B-1$ 的任意顺序，只要相邻数字不同即可。通常使用最简单的递增顺序。

递归步骤：已知 $n-1$ 位的超级格雷码序列 $G_{n-1}$，可以构造 $n$ 位的超级格雷码：

1. 将 $G_{n-1}$ 中的每个码字前添加数字 $0$，得到序列 $S_1$
2. 将 $G_{n-1}$ 反向，在每个码字前添加数字 $1$，得到序列 $S_2$
3. 将 $G_{n-1}$ 正向，在每个码字前添加数字 $2$，得到序列 $S_3$
4. 依此类推，数字 $B-1$ 添加时，根据奇偶性决定 $G_{n-1}$ 是正向还是反向

2. 旋转数组法

题解代码采用了一种更巧妙的非递归方法：

旋转数组 rot 的构造

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= m; j++)
        rot[ind++] = val,
                     val = (val + 1) % m;
    val = (val - 1 + m) % m;
}

这个数组的规律是：

• 长度为 $B^2$
• 可以看作是一个 $B \times B$ 的矩阵按行展开
• 每行是 $0 \sim B-1$ 的一个循环移位

码字生成

对于每个数字 $i$ ($0 \le i < B^n$)，其超级格雷码的第 $j$ 位（从高位到低位）为：

int digit = n - j;
int shang = i / pow(m, digit - 1);
shang %= m * m;
output rot[shang];

这等价于：

1. 将 $i$ 看作 $B$ 进制数
2. 对于第 $j$ 位，取 $i$ 的 $B$ 进制表示中从该位开始的两个连续数字
3. 用这两个数字作为索引在 rot 数组中查找

---

算法正确性

1. 相邻码字的差异性

设当前码字为 $a_{n-1}a_{n-2}\ldots a_0$，其 $B$ 进制值为 $x$，则：

• 下个码字的 $B$ 进制值为 $x+1$
• 当 $x$ 增加 $1$ 时，其 $B$ 进制表示中通常只有最低位变化
• 由于 rot 数组的构造特性，这会导致恰好一位的 $B$ 进制数字发生变化

2. 完备性证明

算法生成了所有 $B^n$ 个不同的 $n$ 位 $B$ 进制数：

• 对于每个 $i$ 从 $0$ 到 $B^n-1$，输出一个唯一的码字
• 不同 $i$ 值生成不同的码字
• 所有码字覆盖了全部 $B^n$ 种可能

3. 格雷码性质的保持

算法的核心在于 rot 数组的设计，它确保了：

• 当 $i$ 的 $B$ 进制最低位从 $k$ 变为 $(k+1)\mod B$ 时
• 对应码字的某一位发生变化，且其他位保持不变

---

复杂度分析

时间复杂度

• 预处理：构造 rot 数组需要 $O(B^2)$，由于 $B \le 36$，最多 $1296$ 次操作
• 生成序列：输出 $B^n$ 个码字，每个码字 $n$ 位，总操作数为 $O(n \cdot B^n)$
• 在数据范围内完全可接受（$B^n \le 65535$）

空间复杂度

• 旋转数组：$O(B^2)$，最多 $1296$ 个整数的存储
• 临时变量：常数空间
• 非常高效

---

实现细节

1. 数字到字符的转换

当 $B > 10$ 时，需要使用字母表示数字 $10 \sim 35$：

if (rot[shang] <= 9)
    cout << rot[shang];
else
    cout << (char)(rot[shang] - 10 + 'A');

2. 循环控制

• 外层循环：$i$ 从 $0$ 到 $B^n-1$
• 内层循环：$j$ 从 $0$ 到 $n-1$，生成每一位
• 注意幂运算可以使用整数运算避免浮点误差

---

算法优势

1. 非递归实现：避免了递归调用的开销
2. 常数时间生成：每个码字的生成时间是 $O(n)$，与序列长度无关
3. 内存友好：只需要存储 $B^2$ 的旋转数组
4. 代码简洁：实现简单，不易出错

---

算法标签

• 排列组合
• 格雷码
• 模拟
• 构造
• 搜索

---

总结

本题的解法展示了一种优雅的非递归格雷码构造方法。通过精心设计的旋转数组，将复杂的序列生成问题转化为简单的查表操作。这种方法不仅正确性易于证明，而且实现简单、效率高，完美满足了题目的所有要求。超级格雷码的构造是经典格雷码的自然推广，体现了组合数学中的对称美与递归结构，是理解数字编码和组合构造的优秀范例。