LG#P5657. [CSP-S 2019] 格雷码

[CSP-S 2019] 格雷码

P5657 [CSP-S 2019] 格雷码

题目描述

\hspace{15pt}通常,人们习惯将所有 nn 位二进制串按照字典序排列,例如所有 22 位二进制串按字典序从小到大排列为 "00"\texttt{"00"}、"01"\texttt{"01"}、"10"\texttt{"10"}、"11"\texttt{"11"}。

\hspace{15pt}格雷码(Gray Code)是一种特殊的 nn 位二进制串排列法,它要求相邻的两个二进制串间恰好有一位不同。特别地,第一个串与最后一个串也算作相邻。

\hspace{15pt}所有 22 位二进制串按格雷码排列的一个例子为 "00"\texttt{"00"}、"01"\texttt{"01"}、"11"\texttt{"11"}、"10"\texttt{"10"}。

\hspace{15pt}nn 位格雷码不止一种,下面给出其中一种格雷码的生成算法:

1. {\hspace{20pt}}_\texttt{1.}\,11 位格雷码由两个 11 位二进制串组成,顺序为 "0"\texttt{"0"}、"1"\texttt{"1"}。

2. {\hspace{20pt}}_\texttt{2.}\,n+1n+1 位格雷码的前 2n2^n 个二进制串,可以由依此算法生成的 nn 位格雷码(总共 2n2^n 个 nn 位二进制串)按顺序排列,再在每个串前加一个前缀 "0"\texttt{"0"} 构成。

3. {\hspace{20pt}}_\texttt{3.}\,n+1n+1 位格雷码的后 2n2^n 个二进制串,可以由依此算法生成的 nn 位格雷码(总共 2n2^n 个 nn 位二进制串)按逆序排列,再在每个串前加一个前缀 "1"\texttt{"1"} 构成。

\hspace{15pt}综上,n+1n+1 位格雷码由 nn 位格雷码的 2n2^n 个二进制串按顺序排列再加前缀 "0"\texttt{"0"},和按逆序排列再加前缀 "1"\texttt{"1"} 构成,共 2n+12^{n+1} 个二进制串。另外,对于 nn 位格雷码中的 2n2^n 个二进制串,我们按上述算法得到的排列顺序将它们从 0∼2n−10 \sim 2^n-1 编号。

\hspace{15pt}按该算法,22 位格雷码可以这样推出:

1. {\hspace{20pt}}_\texttt{1.}\,已知 11 位格雷码为 "0"\texttt{"0"}、"1"\texttt{"1"}。

2. {\hspace{20pt}}_\texttt{2.}\,前两个格雷码为 "00"\texttt{"00"}、"01"\texttt{"01"},后两个格雷码为 "11"\texttt{"11"}、"10"\texttt{"10"},合并得到 "00"\texttt{"00"}、"01"\texttt{"01"}、"11"\texttt{"11"}、"10"\texttt{"10"},编号依次为 0∼30 \sim 3。

\hspace{15pt}同理,33 位格雷码可以这样推出:

1. {\hspace{20pt}}_\texttt{1.}\,已知 22 位格雷码为 "00"\texttt{"00"}、"01"\texttt{"01"}、"11"\texttt{"11"}、"10"\texttt{"10"}。

2. {\hspace{20pt}}_\texttt{2.}\,前四个格雷码为 "000"\texttt{"000"}、"001"\texttt{"001"}、"011"\texttt{"011"}、"010"\texttt{"010"},后四个格雷码为 "110"\texttt{"110"}、"111"\texttt{"111"}、"101"\texttt{"101"}、"100"\texttt{"100"},合并得到 "000"\texttt{"000"}、"001"\texttt{"001"}、"011"\texttt{"011"}、"010"\texttt{"010"}、"110"\texttt{"110"}、"111"\texttt{"111"}、"101"\texttt{"101"}、"100"\texttt{"100"},编号依次为 0∼70 \sim 7。

\hspace{15pt}现在给出 n,kn,k,请你求出按上述算法生成的 nn 位格雷码中的 kk 号二进制串。

输入格式

\hspace{15pt}在一行上输入两个整数 $n,k \left(1 \leqq n \leqq 64;\ 0 \leqq k < 2^n\right)$ 分别代表格雷码的位数与需要求出的编号。

输出格式

\hspace{15pt}在一行上输出一个 nn 位二进制串,代表答案。

测试样例

2 3
10

样例 1 解释

\hspace{15pt}22 位格雷码为 "00"\texttt{"00"}、"01"\texttt{"01"}、"11"\texttt{"11"}、"10"\texttt{"10"},编号从 0∼30 \sim 3,因此 33 号串是 "10"\texttt{"10"}。

3 5
111

样例 2 解释

\hspace{15pt}33 位格雷码为 "000"\texttt{"000"}、"001"\texttt{"001"}、"011"\texttt{"011"}、"010"\texttt{"010"}、"110"\texttt{"110"}、"111"\texttt{"111"}、"101"\texttt{"101"}、"100"\texttt{"100"},编号从 0∼70 \sim 7,因此 55 号串是 "111"\texttt{"111"}。

44 1145141919810
00011000111111010000001001001000000001100011

数据范围与提示

\hspace{15pt}对于 50%50\% 的数据,n≦10n \leqq 10;

\hspace{15pt}对于 80%80\% 的数据,k≦5×106k \leqq 5 \times 10^6;

\hspace{15pt}对于 95%95\% 的数据,k≦263−1k \leqq 2^{63}-1。