题目信息
题目来源：CCF 四川省选 2005；
在线评测地址：Luogu#2328；
运行限制：时间不超过 (1.00 extrm{s})，空间不超过 (128 extrm{MiB})；
题目描述
著名的格雷码是指 (2^n) 个不同 (n) 位二进制数（即 (0)~(2^n-1)，不足 (n) 位在前补零）的一个排列，这个排列满足相邻的两个二进制数的 (n) 位数字中最多只有一个数字不同（例如 ( exttt{003}) 和 ( exttt{001}) 就有一个数位不同，而 ( exttt{003}) 和 ( exttt{030}) 有两个数位不同，不符合条件）。例如 (n=2) 时，(( exttt{00}, exttt{01}, exttt{11}, exttt{10})) 就是一个满足条件的格雷码。
所谓超级格雷码就是指 (B^n) 个不同的 (n) 位 (B) 进制数的排列满足上面的条件。
任务：给出 (n) 和 (B)，求一个满足条件的格雷码。对于大于 (9) 的数用 ( exttt{A})~( exttt{Z}) 表示。（分别表示 (10)~(35)）
输入格式
只有一行，为两个整数 (n) 和 (B)。
输出格式
一共 (B^n) 行，每行一个 (B) 进制数，表示你所求得的符合条件的排列。
数据规模与约定
(2le Ble 36)，(1le B^n< 2^{16}=65536)
分析
我们要将二进制拓展到 (B) 进制。
如果你连二进制怎么做都不知道，出门左转慢走不谢。
按照题目中的意思，易证这种生成方法满足格雷码性质。我们可以凑出一个类似的做法：
- (1) 位超级格雷码有 (0,1,2,cdots,B-1) 共 (B) 个。
- (N) 位格雷码由如下算法生成：
- 对于第 (2k) 种，在前面加上 (2k-1)，后面接上逆序的 (N-1) 位超级格雷码；
- 对于第 (2k+1) 种，在前面加上 (2k)，后面接上正序的 (N-1) 位超级格雷码。
我们也可以用证明二进制的方法来证明这个是正确的。这样我们就可以做出来这道题，获得 (100) 分的好成绩。
当然，我们完全有更好的方法，可以在 (mathcal{O}(1)) 的时间内进行转移。即——利用 lowbit 函数。
我们可以观察到，最后一位变化的时间，恰好是标号增加到 (B^{n-1}) 的时候，即 (operatorname{lowbit}_B(t)=B^{n-1})。
所以，我们计算一个 (B) 进制的 lowbit，就可以完成这个优化。如果不是因为输出的原因，上面那个做法就应该错了。
注意事项
- 进行
lowbit操作时，标号应当从 (0) 开始而不是 (1)； - 如果使用后者进行转移，不要忘记在开始时特判；
- 别忘了这道题奇异的输出方式。
Code
#include <cstdio>
using namespace std;
int lowbit(int n, int b)
{
int x = 1, t = 0;
while (!(n % (x * b)))
x *= b, t++;
return t;
}
int bts[16] = {};
int main()
{
int n, b, t = 1;
scanf("%d%d", &n, &b);
for (int i = 0; i < n; i++)
t *= b;
for (int j = 0; j < n; j++)
printf("%c", (bts[j] < 10)? (bts[j] + '0'):(bts[j] - 10 + 'A'));
putchar('
');
for (int i = 1; i < t; i++)
{
bts[lowbit(i, b)] = (bts[lowbit(i, b)] + 1) % b;
for (int j = 0; j < n; j++)
printf("%c", (bts[j] < 10)? (bts[j] + '0'):(bts[j] - 10 + 'A'));
putchar('
');
}
return 0;
}