← 返回题目列表

Codeforces · 1654/F

F. 最小字符串交换

中文机器翻译题面 查看原题

给定一个整数 $$$n$$$ 和一个由 $$$2^n$$$ 英文字母小写字母组成的字符串 $$$s$$$。字符串$$$s$$$的字符为$$$s_0s_1s_2\cdots s_{2^n-1}$$$。

长度为 $$$2^n$$$ 的字符串 $$$t$$$ (其字符由 $$$t_0t_1t_2\cdots t_{2^n-1}$$$ 表示)是 $$$s$$$ 的异解,如果存在整数 $$$j$$$ ($$$0\le j \leq 2^n-1$$$),例如对于每个 $$$0 \leq i \leq 2^n-1$$$,$$$t_i = s_{i \oplus j}$$$ (其中 $$$\oplus$$$ 表示按位异或运算)。

求 $$$s$$$ 按字典顺序排列的最小 xoration。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 18$$$)。

第二行包含一个字符串$$$s$$$,由$$$2^n$$$英文字母的小写字母组成。

输出

打印一行,其中包含 $$$s$$$ 的字典顺序最小排序。

示例

输入 #1

2
acba

输出 #1

abca

输入 #2

3
bcbaaabb

输出 #2

aabbbcba

输入 #3

4
bdbcbccdbdbaaccd

输出 #3

abdbdccacbdbdccb

输入#4

5
ccfcffccccccffcfcfccfffffcccccff

输出#4

cccccffffcccccffccfcffcccccfffff

输入 #5

1
zz

输出 #5

zz

注意

在第一个测试中,$$$s =$$$"acba" 的字典顺序最小排序 $$$t$$$ 是 "abca"。这是一个反演,因为对于 $$$j = 3$$$,

- $$$t_0 = s_{0 \oplus j} = s_3 =$$$ "a";
- $$$t_1 = s_{1 \oplus j} = s_2 =$$$ "b";
- $$$t_2 = s_{2 \oplus j} = s_1 =$$$ "c";
- $$$t_3 = s_{3 \oplus j} = s_0 =$$$“a”。

在第二个测试中,最小字符串 xoration 对应于在 xoration 的定义中选择 $$$j = 4$$$。

在第三个测试中,最小字符串 xoration 对应于在 xoration 的定义中选择 $$$j = 11$$$。

在第四个测试中,最小字符串 xoration 对应于在 xoration 的定义中选择 $$$j = 10$$$。

在第五个测试中,最小字符串 xoration 对应于在 xoration 的定义中选择 $$$j = 0$$$ 或 $$$j = 1$$$。