CF1163E Magical Permutation【线性基，构造】

题目描述：输入一个大小为\(n\)的正整数集合\(S\)，求最大的\(x\)，使得能构造一个\(0\)到\(2^x-1\)的排列\(p\)，满足\(p_i\oplus p_{i+1}\in S\)

数据范围：\(n,S_i\le 2^{18}\)

什么？NTF在很多年前就把这东西给切了？

首先要把\(S\)缩成一个大小为\(x\)的线性无关组，而且每个数\(<2^x\)，这样就可以构造出\(p\)了。（之后再说）

直接丢进线性基里就可以了吗？不行，应该是把\(<2^x\)的数全部加进去之后，看是不是填满了（有\(x\)个数），填满了就可以。

那现在的问题是怎么构造\(p\)，发现每个\(d_i=p_i\oplus p_{i+1}\in S\)，所以\(p_i\)是由\(S\)的子集异或出来的，而\(S\)是线性无关组就能保证异或出来的两两不同（恰有\(2^x\)个数）且无法更大。

所以就要构造\(S\)的子集构成的序列，使得相邻两个只差一个元素。有一个很妙的方法，先递归到两边分别计算（\([0,2^{x-1})\)和\([2^{x-1},2^x)\)），然后给右半边异或上\(S_x\)就可以满足这个条件了。

#include<bits/stdc++.h>

#define Rint register int

using namespace std;

const int N = 1 << 18;

int n, m, k, cnt, S[N], ans[N], x[19], a[19];

inline void insert(int val){

	int tmp = val;

	for(Rint i = 18;~i;i --)

		if((val >> i) & 1){

			if(x[i]) val ^= x[i];

			else {x[i] = val; a[i] = tmp; ++ cnt; return;}

		}

}

inline void dfs(int dep){

	if(dep == -1) return;

	dfs(dep - 1); ans[++ m] = a[dep]; dfs(dep - 1);

}

int main(){

	scanf("%d", &n);

	for(Rint i = 1;i <= n;i ++) scanf("%d", S + i);

	sort(S + 1, S + n + 1);

	for(Rint i = 1, j = 1;j < 19;j ++){

		while(i <= n && S[i] < (1 << j)) insert(S[i ++]);

		if(cnt == j) k = j;

	}

	printf("%d\n", k);

	dfs(k);

	for(Rint i = 0;i < (1 << k);i ++){

		if(i) ans[i] ^= ans[i - 1];

		printf("%d ", ans[i]);

	}

}

巴特西

CF1163E Magical Permutation【线性基，构造】

最新文章

热门文章