CF - D. Ehab and the Expected XOR Problem（前缀异或）

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

题意
给定两个数 n 和 x，构造一个满足下列条件的数组 a[]：

• $1\le a_i<2^n$；
• 不存在某个非空子段的异或和为 0 或者 x；
• 数组长度尽可能长。

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

思路
如果已经构造出前 n-1 个位置，那么对于第 n 个位置来说：

• 前 n 个位置的异或和 s[n] 不能在前面某个位置作为前缀异或和出现过；
  如果在第 t 个位置出现过，那么区间 [t+1, n-1] 这段区间的异或和就为 0，不满足。
• 前 n 个位置的异或和 s[n] ^ x 不能再前面某个位置作为前缀异或和出现过；
  如果出现过，区间 [t+1, n-1] 的区间异或和就为 x，不满足。

假设当前位置的前缀异或为 y，那么一定要保证 y 和 y^x 没在前面出现过。所以 y 和 y^x 只能有一个作为前缀异或出现在答案数组中，两两配对，和其他值互不影响。
所以这些作为前缀异或的值的顺序没有要求，随意确定一种顺序即可。

如果一种前缀异或的性质确定了，那么原数组也就确定了：s[i] ^ s[i-1] 便是 a[i]。

所以对于每个位置，可以从小到大枚举前缀异或 s[i]，如果当前值在之前没有作为前缀异或出现过，并且其异或上 x 也没有出现过，那么这个值就可以作为前缀异或。

如果每个位置都枚举一遍 $2^{18}$ 个数的话，复杂度很高。
发现如果当前枚举的值不满足要求的话，这个值在后面的位置一定用不到，因为一直要保证这个值在前面没有出现。所以可以用一个指针指向枚举的数，单调往后走。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 2000010, mod = 1e9+7;
int T, n, m;
int a[N], b[N];

signed main(){
	Ios;
	int x;
	cin >> n >> x;
	
	int now = 0, idx = 0;
	
	mp[0] = 1;
	while(now + 1 < 1<<n)
	{
		now ++;
		if(mp[now] || mp[now ^ x]) continue;
		a[++idx] = now;
		b[idx] = now ^ a[idx - 1];
		mp[now] = 1;
	}
	
	cout << idx << endl;
	for(int i=1;i<=idx;i++) cout << b[i] << " ";
	
	return 0;
}
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

经验

• 对于连续区间的异或值有要求，要想到前缀异或。
• 毕竟异或的负负得正性质 x ^ y ^ y = x。