难度不小但没了解过线性代数也不会特别难。没学过向量的就把向量当成正常的二进制数然后进行正常的异或运算即可。0.先行介绍考虑将 n 个数二进制下看成 n 个向量每个向量中的每个元素仅有 0、1 两种取值。如果向量 X 能被​ 这些向量通过异或运算得到则称 X 能被表出。如果某个向量集合中存在若干个向量能被其它向量表出则这些向量线性相关否则线性无关。定义一个向量集合的线性基为其极大线性无关子集可能有多个线性基没关系。也就是说线性基是原向量集合假设为 S的子集。而极大指的是不能再多了。如果你试图往这个线性基里再加入 S 中的任何一个其他向量这个新组就立刻变成“线性相关”的了即新加的那个能被旧的拼出来。线性基和异或运算是强相关的线性基里向量进行异或运算得出的向量即为原向量集合的向量进行异或运算得出的结果。一个向量集合内的线性基可能有多种但线性基的大小即秩是唯一的。感性理解1.模板贪心解法P3812 【模板】线性基 - 洛谷 (luogu.com.cn)先放代码#includebits/stdc.h using namespace std; typedef long long LL; const int N 55; LL p[N]; void insert(LL x) { for (int i 51; i 0; i --) if ((1ll i) x) { // 保证第 i 位为 1 if (p[i]) { x ^ p[i]; // 否则用已有基消去这一位 } else { // 此位没有基插入并结束 p[i] x; return ; // 马上退出总不能一个数值放进两个 p 吧 // 如果放两个最后累积答案时就会累积两次 } } } int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; memset(p, 0, sizeof(p)); for (int i 1; i n; i ) { LL x; cin x; insert(x); } LL ans 0; for (int i 51; i 0; i --) { if ((ans ^ p[i]) ans) { // 如果异或上 p[i] 能让答案变大即让这一位变成 1就进行异或 ans ^ p[i]; } } cout ans \n; return 0; }首先我们要求出线性基最后再用贪心进行取舍得到最大异或和。p[i] 存储的是一个最高位恰好是第i位的数值。void insert(LL x) { for (int i 51; i 0; i --) if ((1ll i) x) { // 保证第 i 位为 1 if (p[i]) { x ^ p[i]; // 否则用已有基消去这一位 } else { // 此位没有基插入并结束 p[i] x; return ;// 马上退出总不能一个数值放进两个 p 吧 // 如果放两个最后累积答案时就会累积两次 } } }如果 x 和当前 p 集合里存着的线性基是线性相关的就会在一次次与 p[i] 异或之后变成 0。这样就能保证求出来的一定是线性基。然后我们贪心从二进制高位到低位如果当前位能被异或为 1就异或。能保证得到最大值。LL ans 0; for (int i 51; i 0; i --) { if ((ans ^ p[i]) ans) { // 如果异或上 p[i] 能让答案变大即让这一位变成 1就进行异或 ans ^ p[i]; } }2.高斯消元求异或集合第 K 大向量线性无关很明显能想到高斯消元。因为当你解一个方程时做的两行相加减消元就类似向量之间相互异或消除线性相关。不了解的可以先去看看高斯消元模板题虽然没多大关系但思想内核相同。【线性代数入门 | 那忘算 8】洛谷 P3389 高斯消元内附行列式教学_高斯消元求行列式-CSDN博客直接看注释代码#includebits/stdc.h using namespace std; typedef long long LL; const int N 55; LL p[N]; LL flg; void insert(LL x) { for (int i 51; i 0; i --) if (x (1ll i)) { if (p[i]) { x ^ p[i]; } else { p[i] x; return; } } if (x 0) { flg 1; // flg 代表着可以异或出 0 } } LL query(LL k) { // 注意这里 k 要longlong k - flg; // 如果能异或出 0那么第 1 小就是 0k - 1 LL ans 0; // 剩下的 p 数组都是 2 的幂次因为只有最高位为 1 // 即如 1,2,4,8,16,32,... // 有可能缺几个p[i] 0 的情况比如说少了 8 // 但这没关系因为不同二进制位不影响 // 类似单个硬币凑面值 // 硬币 1 面值为 1硬币 2 面值为 2硬币 3 面值为 4硬币 4 面值为 8... // 第一小硬币 1 // 第二小硬币 2 // 第三小硬币 1 2 // 第四小硬币 3 // 第五小硬币 3 1 // ... // 发现硬币种类的选择就对应第 K 小的 K 二进制位 for (int i 0; i 51; i ) if (p[i]) { if (k 1) { ans ^ p[i]; } k 1; } if (k) { return -1; } return ans; } int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; memset(p, 0, sizeof(p)); flg 0; for (int i 1; i n; i ) { LL x; cin x; insert(x); } // 类高斯消元 // 从小到大处理 p 数组 // 用比 i 小的 p 数值将 p[i] 里的 1 异或掉 // 只留最高位即第 i 位 本身 // 因为 j i 所以 p[j] 也被处理过即只留第 j 位本身 // 当然也有 p[j] 0 的情况即原本向量集合中没有第 j 位为 1 的数值 // 带进去算一下发现会直接跳过 for (int i 0; i 51; i ) { for (int j 0; j i; j ) { if (p[i] (1ll j)) { p[i] ^ p[j]; } } } int q; cin q; for (int i 1; i q; i ) { LL k; // k 要 longlong cin k; cout query(k) \n; } return 0; }