「CSP2019 T」格雷码
背景
- Idea: CCF
- Data: CCF
- Solution: CCF
- 题面: CCF + oistream
描述
通常,人们习惯将所有 \(n\) 位二进制串按照字典序排列,例如所有 \(2\) 位二进制串按字典序从小到大排列为: 00
,01
,10
,11
。
格雷码(Gray Code)是一种特殊的 \(n\) 位二进制串排列法,它要求相邻的两个二进制串间 恰好 有一位 不同 ,特别的,第一个串与最后一个串也算作相邻。
所有 \(2\) 位二进制串按格雷码排列的一个例子为: 00
,01
,11
,10
。
\(n\) 位格雷码不止一种,下面给出其中一种格雷码的生成算法:
- \(1\) 位格雷码由两个 \(1\) 位二进制串组成,顺序为:
0
,1
。 - \(n+1\) 位格雷码的前 \(2^n\) 个二进制串,可以由依此算法生成的 \(n\) 位格雷码(总共 \(2^n\) 个 \(n\) 位二进制串)按 顺序 排列,再在每个串前加一个前缀
0
构成。 - \(n+1\) 位格雷码的后 \(2^n\) 个二进制串,可以由依此算法生成的 \(n\) 位格雷码(总共 \(2^n\) 个 \(n\) 位二进制串)按 逆序 排列,再在每个串前加一个前缀
1
构成。
综上,\(n+1\) 位格雷码,由 \(n\) 位格雷码的 \(2^n\) 个二进制串按顺序排列再加前缀 0
,和按逆序排列再加前缀 1
构成,共 \(2^{n+1}\) 个二进制串。另外,对于 \(n\) 位格雷码中的 \(2^n\) 个 二进制串,我们按上述算法得到的排列顺序将它们从 \(0\sim 2^n-1\) 编号。
按该算法,\(2\) 位格雷码可以这样推出:
- 已知 \(1\) 位格雷码为
0
,1
。 - 前两个格雷码为
00
,01
。后两个格雷码为11
,10
。合并得到00
,01
,11
,10
,编号依次为 \(0\sim 3\)。
同理,\(3\) 位格雷码可以这样推出:
- 已知 \(2\) 位格雷码为:
00
,01
,11
,10
。 - 前四个格雷码为:
000
,001
,011
,010
。后四个格雷码为:110
,111
,101
,100
。合并得到:000
,001
,011
,010
,110
,111
,101
,100
,编号依次为 \(0\sim 7\)。
现在给出 \(n\),\(k\),请你求出按上述算法生成的 \(n\) 位格雷码中的 \(k\) 号二进制串。
输入格式
仅一行两个整数 \(n\),\(k\),意义见题目描述。
输出格式
仅一行一个 \(n\) 位二进制串表示答案。
样例
输入样例1
2 3
输出样例1
10
输入样例2
3 5
输出样例2
111
输入样例3
44 1145141919810
输出样例3
00011000111111010000001001001000000001100011
样例解释
样例解释1
\(2\) 位格雷码为:00
,01
,11
,10
,编号从 \(0\sim 3\),因此 \(3\) 号串是 10
。
样例解释2
\(3\) 位格雷码为:000
,001
,011
,010
,110
,111
,101
,100
,编号从 \(0\sim 7\),因此 \(5\) 号串是 111
。
数据规模与约定
对于 \(50\%\) 的数据,\(n\leq 10\)。
对于 \(80\%\) 的数据,\(k\leq 5\times 10^6\)。
对于 \(95\%\) 的数据,\(k\leq 2^{63}-1\)。
对于 \(100\%\) 的数据,\(1\leq n\leq 64,0\leq k\leq 2^n\),时间限制 \(1~~\text{s}\),空间限制 \(256~~\text{MB}\)。
相关
在下列训练计划中: