题解 P2328 【[SCOI2005]超级格雷码】

构造方法

对于n进制的数，我们可以构造一个长为$n^2$的循环，

0 1 2 3 ... n-1

n-1 0 1 2 ... n-2

n-2 n-1 0 1 ... n-3

......

1 2 3 4 ... 0.

对于最后一位，直接按照这样的方式循环。

对于倒数第二位，每个数字重复出现 $n$ 次。

对于倒数第三位，每个数字重复出现 $n^2$ 次。

以此类推。

举例解释

输入 n=3,m=3:

（循环节是 012201120）

输出：

000 001 002 012 010 011 021 022 020 120 121 122 102 100 101 111 112 110 210 211 212 222 220 221 201 202 200

代码

按照方法模拟即可：

/*
 * @Author: junyu33 
 * @Date: 2020-05-12 00:29:42 
 * @Last Modified by:   junyu33 
 * @Last Modified time: 2020-05-12 00:29:42 
 */
#include <bits/stdc++.h>
using namespace std;
int rot[10000],ind,val;
int n,m;
int main(){
   cin>>n>>m;
   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;
   }
   for(int i=0;i<pow(m,n);i++){
      for(int j=0;j<n;j++){
         int digit=n-j;
         int shang=i/pow(m,digit-1);
         shang%=m*m;
         if(rot[shang]<=9) cout<<rot[shang];
         else cout<<(char)(rot[shang]-10+'A');
      }
      cout<<endl;
   }
   return 0;
}