题解 P7949 左方之地

zimujun · 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)。