题解：P7949 [✗✓OI R1] 左方之地
He_XY
·
·
题解
大战本题 45 min 终于玩出来了。
本文简称 \text{popcount}(x) 为 pc(x)。
首先 k 为偶数时无解，因为 pc(x) + pc(y) \equiv pc(x \oplus y)\pmod2，那么对于任意相邻两项，pc(a_i) \equiv pc(a_{i-1})\pmod 2，这显然是不可能构成一个排列的。
设原问题为 f(n,k)，考虑 f(n,k) 能否规约到
把值域分为两个部分：$[0, 2^{n-1}), [2^{n-1}, 2^n)$，左半部分的最高位都是 $0$，右半部分都是 $1$，这样左右就分别规约成了 $f(n - 1, k)$，只要分割点处异或起来满足要求就可以。
- $n<k$ 肯定是不行的，因为位数不够。
- $n=k$ 只能在两个数 $x$ 和 $2^n-1-x$ 之间来回跳，因此只有 $n=k=1$ 是可以的。
因此在 $n>k$ 的可行情形下，递归下降时遇到的最小 $n$ 是 $n=k+1$，将其作为 base case。
问题转化成了，构造一个首项为指定值 $x$ 的，$[0, 2^n)$ 的排列，使得 $pc(a_i\oplus a_{i-1}) = n-1$。
观察发现，这个东西非常像格雷码。我们可以在格雷码的基础上，把奇数下标上 $a_i$ 的 01 翻转，偶数下标上的不变。
具体地，原格雷码序列为 $g_i=x\oplus i \oplus \lfloor \frac{i}{2} \rfloor$，$i\in[0,2^n)$。
现令：
$$
a_i=\begin{cases}
g_i, & i \equiv 0 \pmod 2\\
g_i\oplus (2^n-1), & i \equiv 1 \pmod 2
\end{cases}
$$
这样，肯定满足了 $pc(a_i\oplus a_{i-1}) = n-1$ 的条件，但是，它还是一个排列吗？
:::success[证明]
我们已经限制了 $k$ 为奇数，因此 $n$ 为偶数。由于 $pc(x) + pc(y) \equiv pc(x \oplus y)\pmod2$，所以，$pc(g_i)$ 的奇偶性是交替出现的，即：$pc(g_i) \equiv 1 - pc(g_{i-1}) \pmod2$。
奇数下标上的数的 popcount 奇偶性相同，翻转后奇偶性仍然不变且相同。所以此时仍然构成 $[0, 2^n)$ 的排列。
:::
在 base case 的时候，构造一个奇数下标翻转了的格雷码序列；每次递归时，在分割点处，可以直接令右半部分的首项，等于左半部分的末项的最低 $k-1$ 位翻转后的值（注意是 $k-1$ 不是 $k$，因为最高位已经不同）。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int> grey(int x, int n){
vector<int> ans;
for (int i = 0; i < (1 << n); i++){
int cur = x ^ i ^ (i >> 1);
if (i & 1) ans.emplace_back(cur ^ (1 << n) - 1);
else ans.emplace_back(cur);
}
return ans;
}
vector<int> solve(int n, int k, int x){
if (n == k + 1) return grey(x, n);
vector<int> ans = solve(n - 1, k, x);
int p = ans.back() ^ (1 << k - 1) - 1;
vector<int> b = solve(n - 1, k, p);
for (int x : b) ans.emplace_back(x ^ (1 << n - 1));
return ans;
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k;
if (n == 1 && k == 1) return cout << "1\n0 1\n", 0;
if (k % 2 == 0 || k >= n) return cout << "0\n", 0;
cout << "1\n";
vector<int> ans = solve(n, k, 0);
for (int x : ans) cout << x << " "; cout << endl;
return 0;
}
```