AtCoder ARC138D – Differ by K bits 简略题解

考虑这个排列是怎样生成的。转述一下题意，可以发现，$\operatorname{popcount}(P_i \oplus P_{i+1 \mod {2^n}})=K$，也即全集$\text{msk}=2^N-1$的一个大小为$K$的子集。

由于这是一个环排列，我们不妨令$P_0=0$。这样一来，$P_i=\operatorname{\bigoplus}\limits_{j=1}^{i}S_j, |S_j|=K$。结合上文可知，这是一个相邻元素二进制位恰相差$K$位的格雷码问题。有$K=1$时，满足条件的$S_j$恰有$N$个，也就是$N$位格雷码。

考虑推广。我们发现，如果按照类格雷码的方式生成排列，则所有的$S_j$应构成异或空间，其大小应当恰为$2^N$，并且由线性空间知识可以得到，该线性空间的秩（基的大小）应当恰为$N$。这恰好符合$N$位格雷码的构造。因此，只要满足上述条件，就一定能够生成符合题意的排列。

可以证明，除了$2\mid K \lor (K=N \land N>1)$以外，总是有满足条件的线性空间生成的。

下述解法的时间复杂度$\operatorname{O}\left(\dbinom{N}{K}+2^N\right)$。

Submission #30901272

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

#define inl inline
template <typename T> inl bool read (T &x) {
	x = 0; int f = 1; char c = getchar ();
	for (; c != EOF && !isdigit (c); c = getchar ())
		if (c == '-') f = -1;
	if (c == EOF) return 0;
	for (; c != EOF && isdigit (c); c = getchar ())
		x = (x<<1) + (x<<3) + (c^48);
	x *= f; return 1;
}
template <typename T, typename... Targs>
inl bool read (T &x, Targs&... args) {
	return read (x) && read (args...); }
template <typename T> void print (T x) {
	if (x < 0) putchar ('-'), x = -x;
	if (x > 9) print (x / 10);
	putchar ('0' + x % 10);
}
template <typename T, typename... Targs>
inl void print (T x, Targs... args) {
	print (x), putchar (' '), print (args...); }

#define reint register int
#define newl putchar('\n')
typedef long long ll;
// typedef unsigned long long ull;
// typedef __int128 lll;
// typedef long double llf;
typedef pair <int, int> pint;
#define fst first
#define scd second
#define all(p) (p).begin (), (p).end ()

constexpr int N = 18, G = 3e5 + 10;
int n, k, p[G], lst[G], lcnt, seq[G];
int gen[G], a, gcnt, basis[G], bcnt; bool vis[G];

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

int main () {
	/* ARC138D - Differ by K bits 吴秋实 */
	read (n, k);
	if (n == k && n > 1) return puts ("No"), 0;
	for (int msk = (1<<k) - 1; msk < 1<<n;) {
		lst[++lcnt] = msk;
		int l = lowbit (msk), p = l + msk;
		msk = ((msk & ~p) / l >> 1) + p;
	}
	vis[0] = 1, gen[gcnt = 1] = 0;
	for (int i = 1; i <= lcnt; ++i) {
		if (vis[lst[i]]) continue;
		basis[++bcnt] = lst[i];
		for (int j = 1; j <= gcnt; ++j)
			gen[gcnt + j] = gen[j] ^ lst[i],
			vis[gen[gcnt + j]] = 1;
		gcnt <<= 1;
	}
	if (gcnt != (1<<n)) return puts ("No"), 0;
	for (int i = 0; i < n; ++i) {
		seq[1<<i] = i + 1;
		for (int j = 1; j < 1<<i; ++j)
			seq[(1<<i) + j] = seq[j];
	}
	puts ("Yes");
	printf ("%d ", a = 0);
	for (int i = 1; i < 1<<n; ++i)
		printf ("%d ", a = a ^ basis[seq[i]]);

	return 0;
}