306208: CF1163E. Magical Permutation

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Magical Permutation

题意翻译

Kuro选择了$n$个不同的数作为集合$S$。定义一种排列,满足以下条件: 1、排列中的数$p\in[0,2^x-1]$; 2、排列中任意两个相邻的元素的异或值为集合$S$的一个数。 现在Kuro告诉你集合$S$中的数,想请你构造一个满足条件的排列,使得 $x$ 最大。 【输入】 第一行一个整数$n$,接下来一行$n$个整数$S_i$表示集合$S$的数。 【输出】 第一行一个整数$x$,接下来一行$2^x$个数,表示你构造的排列。若有多种排列,输出任意一种即可。

题目描述

Kuro has just learned about permutations and he is really excited to create a new permutation type. He has chosen $ n $ distinct positive integers and put all of them in a set $ S $ . Now he defines a magical permutation to be: - A permutation of integers from $ 0 $ to $ 2^x - 1 $ , where $ x $ is a non-negative integer. - The [bitwise xor](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of any two consecutive elements in the permutation is an element in $ S $ . Since Kuro is really excited about magical permutations, he wants to create the longest magical permutation possible. In other words, he wants to find the largest non-negative integer $ x $ such that there is a magical permutation of integers from $ 0 $ to $ 2^x - 1 $ . Since he is a newbie in the subject, he wants you to help him find this value of $ x $ and also the magical permutation for that $ x $ .

输入输出格式

输入格式


The first line contains the integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the number of elements in the set $ S $ . The next line contains $ n $ distinct integers $ S_1, S_2, \ldots, S_n $ ( $ 1 \leq S_i \leq 2 \cdot 10^5 $ ) — the elements in the set $ S $ .

输出格式


In the first line print the largest non-negative integer $ x $ , such that there is a magical permutation of integers from $ 0 $ to $ 2^x - 1 $ . Then print $ 2^x $ integers describing a magical permutation of integers from $ 0 $ to $ 2^x - 1 $ . If there are multiple such magical permutations, print any of them.

输入输出样例

输入样例 #1

3
1 2 3

输出样例 #1

2
0 1 3 2 

输入样例 #2

2
2 3

输出样例 #2

2
0 2 1 3 

输入样例 #3

4
1 2 3 4

输出样例 #3

3
0 1 3 2 6 7 5 4 

输入样例 #4

2
2 4

输出样例 #4

0
0 

输入样例 #5

1
20

输出样例 #5

0
0 

输入样例 #6

1
1

输出样例 #6

1
0 1 

说明

In the first example, $ 0, 1, 3, 2 $ is a magical permutation since: - $ 0 \oplus 1 = 1 \in S $ - $ 1 \oplus 3 = 2 \in S $ - $ 3 \oplus 2 = 1 \in S $ Where $ \oplus $ denotes [bitwise xor](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) operation.

Input

题意翻译

Kuro选择了$n$个不同的数作为集合$S$。定义一种排列,满足以下条件: 1、排列中的数$p\in[0,2^x-1]$; 2、排列中任意两个相邻的元素的异或值为集合$S$的一个数。 现在Kuro告诉你集合$S$中的数,想请你构造一个满足条件的排列,使得 $x$ 最大。 【输入】 第一行一个整数$n$,接下来一行$n$个整数$S_i$表示集合$S$的数。 【输出】 第一行一个整数$x$,接下来一行$2^x$个数,表示你构造的排列。若有多种排列,输出任意一种即可。

加入题单

上一题 下一题 算法标签: