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;
}