自动搬运

查看原文

来自洛谷，原作者为

	zimujun 有时不是号主本人上线。

搬运于2025-08-24 22:34:34，当前版本为作者最后更新于2021-11-18 14:54:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由线性基的相关知识可知，只要能够在 $[0, 2^n)\cap \mathbb Z$ 中找到 $n$ 个在异或运算下线性无关的数，那么这所有的 $2^n$ 个数都能通过这些数互相异或表示出来，称这 $n$ 个数为基底。

在本题中，只要选取所有满足 $\operatorname{popcount(x)} = k$ 的数插入线性基，记录所有成功插入的数和成功插入的数作为基底，若成功插入的数小于 $n$ 个则无解。

另一个问题，为了保证相邻两个数只有一个基底的差异，使用格雷码（相邻两数只有一位的差异）表示每个基底存在的状态即可。

时间复杂度 $O(n \log n)$。