题解：CF1163E Magical Permutation

SFlyer · 2024-12-26 22:08:12 · 题解

很少在 duel 的时候遇到惊艳我的 2400 了。正好把我不熟的整合了一下。

• 首先假设我们 S 可以自己定，如果要满足 0\sim 2^x-1 的，|S| 最小是多少？

|S| 最小是 x。考虑 S=\{0,1,2,\cdots ,2^{x-1}\}。然后我们 0,1,3,2,\cdots 构造序列。容易证明 |S| 不可能更小。

一点要注意的是，0,1,3,2,\cdots 是格雷码。

• 给定 S，怎么判断一个 x 合不合法？

其实也就是 S 中的集合能不能表示所有 0\sim 2^x-1，并且不重不漏。

一个显然的条件是 S 中有用的数插入线性基中，线性基大小 =x。

然后发现这个是冲要条件：

• 首先，所有 0\sim 2^x-1 可以用线性基中若干个数 \oplus 得到。

• 其次，根据线性基的定义：没有两个子集异或相等，所以 0\sim 2^x-1 的数都可以以唯一方式表示出来。定义这个数的编号为：一个二进制串，每一位表示选不选这个线性基中的数。

• 因为有 2^x 个数，而线性基最多能表示 2^x 个数，所以数和编号是双射关系。

• 因为是不重不漏的 000,001,010,011,\cdots，所以可以构成一个格雷码。

那么构造也简单了：可以直接暴力搜索，一定有答案。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 4e5+5;

int n,a[N],b[20],c[20],cnt,mx;

void ins(ll x){
    ll y=x;
    for (int i=19; i>=0; i--){
        if (x>>i&1){
            if (!b[i]){
                b[i]=x;
                c[i]=y;
                cnt++;
                return;
            }
            else{
                x^=b[i];
            }
        } 
    } 
}

int vis[N];

void dfs(int u){
    cout<<u<<" ";
    vis[u]=1;
    for (int i=0; i<mx; i++){
        if (!vis[c[i]^u]){
            dfs(c[i]^u);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for (int i=1; i<=n; i++){
        cin>>a[i];
    }
    for (int i=19; i>=0; i--){
        cnt=0;
        for (int j=0; j<20; j++) b[j]=c[j]=0;
        for (int j=1; j<=n; j++){
            if (a[j]<=(1<<i)-1){
                ins(a[j]);
            }
        }
        if (cnt==i){
            mx=i;
            cout<<i<<"\n";
            dfs(0);
            return 0;
        }
    }
    return 0;
}