Codeforces 1163E (线性基)

Codeforces 1163E
题意：给定集合$S$, 求出一个$x$最大的$[0, 2^x-1]$排列，使得任意两个相邻元素异或值在$S$中。

设$S$的线性基为$T$
1、$[0, 2^x-1]$可以被构造出来当且仅当$[0, 2^x-1]$中的数可以被小于$2^x-1$的$T$中的元素表示出来

证明：排列中一定有$0$, $0$周围两个数$i,j$肯定$i,j \in S$，那么之后的数都可以类推然后发现就是能被$S$表示既可以，否则不行。那么只需要$T$能表示即可。

运用这个结论，边求出线性基，边计算最大满足条件的$x$

2、构造的排列相邻的两个元素在$T$中映射的bitset相差$1$位

证明：结果比较显然，不相差$1$位就不能从其他位异或一个$S$得到这个数。

那么直接DFS从0开始构造序列即可。

知识点：
1、异或题的0

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 1000000 + 5, len = 20;

    int sz, ans, n, S[MAXN], a[MAXN], vis[MAXN];
    vector<int > vec;

    void add(int t, int op) {
        int oo = t;
        for (int i = len; i >= 0; --i) {
            if (!(t >> i & 1)) continue ;
            if (a[i]) t ^= a[i];
            else {
                for (int j = 0; j < i; ++j) if (t >> i & 1) t ^= a[j];
                for (int j = i + 1; j <= len; ++j) if (a[j] >> i & 1) a[j] ^= t;
                a[i] = t, ++sz;
                if (op) vec.push_back(oo);
                break ;
            }
        }
    }
    void dfs(int x, int num) {
        printf("%d ", x);
        if (num == (1 << ans) - 1) return ;
        for (int i = 0; i < (int)vec.size(); ++i) {
            int val = vec[i];
            if (!vis[x ^ val]) {
                vis[x ^ val] = 1;
                dfs(x ^ val, num + 1);
            }
        }
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n;
        for (int i = 1; i <= n; ++i) scanf("%d", &S[i]);
        sort(S + 1, S + 1 + n);
        int p = 1;
        for (int i = 1; i <= len; ++i) {
            while (p <= n && S[p] < (1 << i)) add(S[p], 0), ++p;
            if (sz == i) ans = i;
        }
        printf("%d\n", ans);
        ms(a, 0);
        for (int i = 1; i <= n && S[i] < (1 << ans); ++i) add(S[i], 1);
        vis[0] = 1, dfs(0, 0);
        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}