Ehab and the Expected XOR Problem

发表于 分类于 ，

    给出n和x，构造一个最长的数组a，使得a的任意子数组的异或和不为0或x。a的元素值$1 \le a_i<2^n$

    $ 1 \le n \le 18, 1 \le x < 2^18$

Ehab and the Expected XOR Problem

Created by LXC on Thu Aug 17 15:15:39 2023

https://codeforces.com/problemset/problem/1174/D

ranting: 1900

tag: bitmasks, constructive algorithms

problem

给出n和x，构造一个最长的数组a，使得a的任意子数组的异或和不为0或x。a的元素值$1 \le a_i<2^n$

$ 1 \le n \le 18, 1 \le x < 2^18$

solution

考虑合法的a数组的前缀异或和数组b。

b的每个元素不能相同，否则两个前缀的异或就是区间的异或，当两个前缀异或和相等则区间异或和为0.

b的任意两个元素异或不能等于x。

我们可以构造出b，然后构造出a。

对于构造b的方法，我们可以遍历1到$2^n$内的数选择一些作为b的元素。遍历保证了b的每个元素不相等。
然后对于当前遍历元素i，如果$i\oplus x$已经是b的元素，那么则i不能作为b的元素。这可以用哈希表实现。

$i$和$i\oplus x$两者独立，任选一个不会影响答案。

code

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

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    vector<int> v(1 << 18);
    v[0] = 1;
    int n, x;
    cin >> n >> x;
    vector<int> a = {0};
    for (int i = 1; i < 1 << n; i++) {
        if (v[x ^ i])
            continue;
        v[i] = 1;
        a.push_back(i);
    }
    cout << a.size() - 1 << endl;
    for (int i = 1; i < a.size(); i++) {
        cout << (a[i - 1] ^ a[i]) << " ";
    }
    cout << '\n';
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}