CF1163E Magical Permutation 题解【线性基】【递归】【构造】

点击量：259

首先恭喜 xht37 喜提本场 rk1。

考场上想到线性基了不会构造…貌似还有一些别的细节

目录

Description

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 xx is a non-negative integer.
• The bitwise 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$.

Input

The first line contains the integer $n$ ($1\le n\le2\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\le S_i\le 2\cdot 10^5$) — the elements in the set $S$.

Output

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.

Examples

input

3
1 2 3

output

2
0 1 3 2 

input

2
2 3

output

2
0 2 1 3 

input

4
1 2 3 4

output

3
0 1 3 2 6 7 5 4 

input

2
2 4

output

0
0 

input

1
20

output

0
0 

input

1
1

output

1
0 1 

Note

In the first example, $0,1,3,2$ is a magical permutation since:

• $0\oplus1=1\in S$
• $1\oplus3=2\in S$
• $3\oplus2=1\in S$

Where $\oplus$ denotes bitwise xor operation.

题意：

给定一个大小为 $n$ 的集合 $S$。

你需要构造一个 $0\sim 2^x-1$ 的排列 $p$，使得 $\forall i\in[0,2^x-1),p_i\oplus p_{i-1}\in S$，同时使得 $x$ 尽可能大。

题解：

构造的排列需要不重不漏，$2^x$ 个元素恰好各出现一次。此时考虑到最大的元素是 $2^x-1$，因此容易联想到大小为 $x$ 的线性基可以恰好表示 $0\sim 2^x-1$ 中的元素。

因此我们考虑构造出 $S_1,S_2,\ldots,S_n$ 的线性基 $bs$。令 $k$ 是最大的满足 $\forall i\in[0,k],bs_i>0$ 的数，则答案就是 $k+1$，因为可以用 $bs_0,bs_1,\ldots,bs_k$ 表示出 $0\sim2^{k+1}-1$ 中所有的数。

由于构造这样的线性基只需要 $k+1$ 个数，每一个 $bs$ 都是可以通过这 $k+1$ 个数异或出来的。所以我们只需要 $S$ 集合中的 $k+1$ 个数。

也就是我们每次只需要异或那 $k+1$ 个数就可以了。

而由此，$bs_0,bs_1,\ldots,bs_k$ 中可以选择任意个数将他们异或起来得到一个新的数 $t$，选择方案是 $2^{k+1}$。那么问题就转化为了如何每次只翻转 $t$ 的一个位，使得恰好在 $2^k-1$ 步遍历完 $1\sim 2^k-1$，初始值 $t=0$。

这就转化为了一个递归问题。假定我们已经有了在 $2^k-1$ 步遍历完 $1\sim2^k-1$ 的方法 $F(k)$，我们现在需要用 $2^{k+1}-1$ 步遍历完 $1\sim 2^{k+1}-1$。我们只需要翻转一下第 $k$ 位，然后再进行一次 $F(k-1)$ 即可。

具体而言，我们来从 $0$ 遍历到 $7$。

我们求出了 $F(0)$，$000_{(2)}\to001_{(2)}$；

然后翻转第 $1$ 位，$001_{(2)}\to011_{(2)}$；

重新调用 $F(0)$，可以把第 $0$ 位到第 $0$ 位都再翻转一遍，得到 $011_{(2)}\to010_{(2)}$。

此时我们得到了 $F(1)$，也就是说，已经知道了如何在 $011_{(2)}$ 步内遍历完 $1\sim011_{(2)}$。回到求 $F(2)$ 的过程。这时应该翻转第 $2$ 位，$011_{(2)}\to111_{(2)}$。然后再进行 $F(1)$ 就可以把第 $2$ 位为 $1$ 的情况都遍历完了。

以此类推，用递归的方式就可以解决问题了。

时间复杂度 $O(n\log n)$。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
using std::vector;
int read()
{
    int x=0,f=1;
    char ch=gc();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=gc();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch&15);
        ch=gc();
    }
    return x*f;
}
int a[200100];
int bs[20];
int t[20],k=0;
void trans(int n)
{
    if(n==-1)
        return;
    trans(n-1);
    k^=t[n];
    printf("%d ",k);
    trans(n-1);
}
int main()
{
#ifdef wjyyy
    freopen("a.in","r",stdin);
#endif
    int n=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    std::sort(a+1,a+1+n);
    for(int i=1;i<=n;++i)
    {
        int u=a[i];
        for(int j=19;j>=0;--j)
        {
            if((u>>j)&1)
            {
                if(bs[j])
                    u^=bs[j];
                else
                {
                    bs[j]=u;
                    t[j]=a[i];
                    break;

                }
            }
        }
    }
    int ans=-1;
    while(bs[ans+1])
        ++ans;
    printf("%d\n0 ",ans+1);
    trans(ans);
    return 0;
}