CF1163E. Magical Permutation

发表于 | 阅读数

输入一个大小为$n$的正整数集合$𝑆$，求最大的$𝑥$，使得能构造一个$0$到$2^x−1$的排列𝑝，满足$𝑝_𝑖⊕p_{i+1}∈𝑆$

可知$p_i \oplus p_{i+k}=S_i …\oplus S_j$，因为存在$0$，即构造一个数列能被表示所有$S$线性基所表示。找到非空的最大线性基，然后要需要判断里面是否存在$lineBase[i]>2^x$。然后瞎$JB$构造一下，保证没有重复即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int MAXL = 20;
class LinearBase
{
public:
    ll p[MAXL];
    int pos[MAXL];
    void clear()
    {
        memset(p, 0, sizeof(p));
    }

    void insert(ll x, int val)
    {

        for (int i = MAXL - 1; i >= 0; i--)
        {
            if (x & (1ll << i))
            {
                if (!p[i])
                {
                    p[i] = x;
                    pos[i] = val;
                    break;
                }
                x ^= p[i];
            }
        }
    }
    ll query_max(ll x = 0)
    {
        ll res = x;
        for (int i = MAXL - 1; i >= 0; i--)
            res = max(res, res ^ p[i]);
        return res;
    }

    ll query_min()
    {
        for (int i = 0; i < MAXL; i++)
            if (p[i])
                return p[i];
        return 0;
    }
    void rebuild()
    {
        for (int i = MAXL - 1; i >= 0; i--)
            for (int j = i - 1; j >= 0; j--)
                if ((p[i] >> j) & 1)
                    p[i] ^= p[j];
    }
    // void mergeFrom(const LinearBase &other)
    // {
    //     for (int i = 0; i <= MAXL; i++)
    //         insert(other.p[i]);
    // }
    ll query_kth(ll k)
    {
        return 0;
    }
} lb;
int a[N], n, v[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(1 + a, 1 + a + n);
    for (int i = 1; i <= n; i++)
        lb.insert(a[i], a[i]);
    int ans = 0;
    while (lb.p[ans])
        ans++;

    while (ans)
    {
        bool flag = 1;
        for (int i = 0; i < ans; i++)
            if (lb.pos[i] > (1 << ans))
            {
                ans = i;
                flag = 0;
                break;
            }
        if (flag)
            break;
    }
    int x = 0;
    printf("%d\n", ans);
    for (int i = 1; i <= 1 << ans; i++)
    {
        printf("%d ", x);
        v[x] = 1;
        for (int j = 0; j < ans; j++)
            if (!v[x ^ lb.pos[j]])
            {
                x ^= lb.pos[j];
                break;
            }
    }
}