CWOI S C0279 B 缘

题意

使用 openssl enc -aes256 -pbkdf2 -a 加密。

U2FsdGVkX19neiVaoznqXKLymVnTkVg1M1tgsIH9Y2jb7uz4JEr6BZhBpWfbhKaW
ofA09hHx3K4U7PanU0LyRml+NMpMg231Iar6Rw440z9vsgGTweJ9F22E6KKBCWl6
zYf47MCOBj9xxzLKFry+ulk8C/5Pl1XtT92mSonCM5q82zXhVCsbir5L1nL8RCD7
ij7hjcIODyuS+SNGdbbiYwmDyXhU7CzKFBtxremW3e0ezgL0Y5zWm/vJd4rPjCDt
SdIE5IpXG/kToQDRExTUYrglMB0oaZfG98SX2MxhnrUmXT/8df2plf9EUp1es5GT
vjqdAzT5N1jt7/OkAl6C8cUSOpg9nLS08wurtCg+tAYpLqP3CMxlFMgwsIokz3z4
owkWtfB8+zCaA+TeY1V+Fg==

解析

我们约定 $\oplus$ 表示按位异或运算，$\mathrm{popcount}$ 表示求某个数二进制表示下 1 的个数。

这个东西很容易让人联想到格雷码。

首先，令 $u' = u \oplus v$，$v' = v \oplus v = 0$，我们的目标就变为了从 $u'$ 变到 0，每次只能变一位，不能重复。当然，如果 $u' = 0$ 了，那自然 $a$ 就只能有 $u$ 一个值了。

考虑固定一位值为 $1$ 的不动，按照格雷码遍历其他 $n-1$ 个没有固定的位的所有情况，遍历完之后，再将固定的那一位变成 $0$，然后就不要在管这个固定的位，转化为了一个 $n-1$ 的子问题。特别的，如果遍历完之后，非固定位全部变成了 $0$，这时就无法在进行下去了，可以考虑反向遍历格雷码。

如果初始时 $\mathrm{popcount}(u')$ 是奇数，那么就可以顺利地按照算法进行，总共遍历了 $2^{n-1} + 2^{n-2} + 2^{n-3} + \cdots + 2^0 + 1 = 2^n$ 个数，取到了上界。而如果 $\mathrm{popcount}(u')$ 是偶数，那么按照上面的方法会遍历到非固定位为 11 的情况，不管怎么遍历，都无法遍历完，只能 11 -> 10 -> 00，一定有一个数无法遍历。

实现

int lowbit(int x)
{
	return x & -x;
}

bool has_bit(int x, int y)
{
	return (bool)((x >> y) & 1);
}

int get_mask(int x, int mask)
{
	int y = 0;
	int cnt = 0;
	while (mask) {
		int k = lowbit(mask);
		mask ^= k;
		int t = (x & k) != 0;
		y |= t << cnt;
		cnt++;
	}
	return y;
}

int fill_mask(int x, int mask)
{
	int y = 0;
	int i = 0;
	while (mask) {
		int k = lowbit(mask);
		mask ^= k;
		y |= k * has_bit(x, i);
		i++;
	}
	return y;
}

int safe_mod(int x, int m)
{
	return (x % m + m) % m;
}

int popcount(int x)
{
	return __builtin_popcount(x);
}

int main()
{
	int n, u, v;
	std::cin >> n >> u >> v;

	if (u == v) {
		std::cout << 0 << std::endl
			<< u << std::endl;
		return 0;
	}

	int N = 1 << n;
	u ^= v;

	std::vector<int> ans;
	ans.emplace_back(u);

	std::vector<int> gray(N), gi(N);
	for (int i = 0; i < N; i++) {
		gray[i] = i ^ (i / 2);
		gi[gray[i]] = i;
	}

	int mask = N - 1;
	int fixed = 0, unfixed_cnt = n;
	while (unfixed_cnt > 2 || (unfixed_cnt > 0 && popcount(u) % 2 == 1)) {
		int p = 0;
		while (p < n && (has_bit(fixed, p) || !has_bit(u, p))) p++;
		assert(p < n);

		fixed |= (1 << p);
		unfixed_cnt--;
		int k = get_mask(u, mask ^ fixed);
		int t = 1 << unfixed_cnt;
		int gk = gi[k];
		int d = 1;
		if (gray[safe_mod(gk - 1, t)] == 0) d = -1;
		for (int i = safe_mod(gk + d, t); i != gk; i = safe_mod(i + d, t)) {
			int next = (u & fixed) | fill_mask(gray[i], mask ^ fixed);
			ans.emplace_back(next);
			u = next;
		}
		ans.emplace_back(u ^ (1 << p));
		u ^= (1 << p);
	}

	if (unfixed_cnt == 2 && popcount(u) == 2) {
		ans.emplace_back((u & fixed) | fill_mask(0b10, mask ^ fixed));
		ans.emplace_back((u & fixed) | fill_mask(0, mask ^ fixed));
	}

	std::cout << ans.size() - 1 << std::endl;
	for (auto i : ans) std::cout << (i ^ v) << " ";
	std::cout << std::endl;
}