嗯。就是主包没过昨晚 ABC G,然后想大学习线性基。
P3812
Difficulty:4.2 / Template
题意解析:给定一个长度为 nnn 的数组 AAA。求 AAA 的子序列异或和最大值。
n≤2×105,0≤Ai<250n\le 2\times 10^5,0\le A_i\lt 2^{50}n≤2×105,0≤Ai <250。
直接做是 O(2n)O(2^n)O(2n) 或 O(nV)O(nV)O(nV) 的,显然过不了。
直觉告诉我们真正要用到的 AiA_iAi 其实是很少的,其它的都能被这些异或表示。
假设当前 A1,...,Ai−1A_1,...,A_{i-1}A1 ,...,Ai−1 能表示 kkk 个数,此时考虑 AiA_iAi 。
* 如果 AiA_iAi 能被前面的数表示,那它就没用了,依然只能表示 kkk 个数。
* 如果 AiA_iAi 不能被前面的数表示,那前面能表示的所有数显然都能异或上 AiA_iAi 变成一个新的数,此时能表示 2k2k2k 个数。
所以真正用到的数的数量不超过 ⌊log2V⌋+1\lfloor\log_2 V\rfloor+1⌊log2 V⌋+1 个。
现在考虑如何构造出这些。
见这个。没了。主要是特别巧妙不知道咋讲。
时间复杂度:O(nlogV)O(n\log V)O(nlogV)。