Atcoder ZEP F题

题意

(;)
给定(n,m)，其中(n=2^k)，再给一个长度为(m)的数组(A)
点(i,j)间可以连边当且仅当(i;xor;j otin A)
问是否有一种方案，使得这(n)个点构成一棵树，构造出这种方案
否则输出-1
(kleq 18)
(;)

Solution

(;)
先考虑是否有解。
我们取出(A)的补集(B)。
你会发现，往外连边实际上就是不断异或上(B)中的元素。
如果有解，当且仅当(b_1,b_2,cdots,b_{n-m})中某些数的异或和能够表示出(0)到(n-1)的所有数
所以，我们可以构造出(B)的线性基，判断线性基大小是否为(k)即可。
(;)
怎么构造方案呢？
因为线性基中的每个元素实际上都可以表示为：成功插入线性基的一部分(b_i)的异或和
所以我们只需要管那些成功插入到线性基中的(b_i)就可以了，而这样的数最多有(log; n)个
(;)
然后我们就从0到(n-1)进行枚举，只使用这(k)个(b_i)，能往外连边就贪心地连，再用并查集维护一下连通性即可。
(;)

Code

#include <bits/stdc++.h>
 
const int N = 500010;
 
int n, m, k, d[20], st[N], cnt, tmp[20], fa[N];
 
void ins(int x) {
	int X = x;
	for (int i = k; ~i; i --) {
		if (!(x >> i & 1)) continue;
		if (d[i]) x ^= d[i];
		else {
			d[i] = x; tmp[i] = X;
			cnt ++;
			return;
		}
	}
}
 
int find(int x) {
	if (fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}
int main() {
	scanf("%d%d", &n, &m);
	k = (int) log2(n);
	for (int i = 1; i <= m; i ++) {
		int x; 
		scanf("%d", &x); st[x] = 1;
	}
	for (int i = 0; i < n; i ++) {
		if (!st[i]) ins(i);
	}
	if (cnt < k) {
		puts("-1");
		return 0;
	}
	for (int i = 0; i < n; i ++) fa[i] = i;
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j <= k; j ++) {
			if (find(i) != find(i ^ tmp[j])) {
				fa[find(i)] = find(i ^ tmp[j]);
				printf("%d %d
", i, i ^ tmp[j]);
			}
		}
	}
	return 0;
}