浅谈异或构造——异或类构造题的小技巧

违规用户名1271019 · 2026-04-25 11:08:44 · 算法·理论

修改墙

修改：感谢 F1raC0de 大犇把我的 case 6 hack 了。

修改：感谢 wjh2022 大犇把我的 case 5 hack 了以及 Zhuan_（我同学）把这个 hack 延申。

修改：新增线性基内容。

修改：修改格式。

其他地方没有改动，求审核大大通过。

文

能把这个帖子 hack 的大犇们必关。私信给 hack 不然太丢脸了。

（我们讨论的数字均为非负整数的二进制）

最近机房的小伙伴一遇到构造题就头疼（包括我），于是就写一写我在异或构造方面的感想，大犇们不喜勿喷。

已严肃求赞。

其中 0x01 到 0x08 为构造，0x0b 会讲讲线性基。

0x00

a\oplus b\le a+b

上来先给个小结论，这个结论大家肯定都听说过，证明也很简单。

对于每一位，若 a，b 同时取 1，则加法会产生进位，而异或不会，异或只会直接变成 0，所以就算没有位 a，b 同时取 1，也只是 a\oplus b=a+b，但一旦有了进位，会有 a\oplus b<a+b。

接下来的证明也会像这样，我不会非常非常像数学一样严谨的证明因为我不会，但是大家应该也能理解为什么会有结论。

先来看看几个小的结论。

以下令 g(x) 为 x 的首位 1 的值（比如 g(5)=4，g(11)=8），f(x)=2\times g(x)-1，即 f(x) 就是让 x 的 0 位变为 1（不包括前导零）。

0x01

第一眼看到是不是炸了？别怕，还有更难的。

通过上面的结论，有 a\oplus b\le a+b，所以我们只需要令 a\oplus b=a+b=A 就行了，显而易见，只要让 a 取 A，b 取 0 就行了。

是不是非常简单？

0x02

我们想让和最大，只需要在 X 的 1 位上让 a 或 b 任意一个取 1，0 位上让 a 和 b 都取 1 就行。

给出构造：a=f(X)\oplus X，b=f(X)。

这样能保证 a\oplus b=f(X)\oplus X\oplus f(X)=X，也能通过贪心证明这样的和是最优的。

0x03

第一眼看上去是不是很不对劲？a\oplus b 最小？

我们先假设 A 是个偶数吧，这样我们很快就想到 —— 两个相同的数异或起来等于 0，所以我们可以让 a 和 b 都取 \frac{A}{2}，这样 a\oplus b 就等于 0 了。

但是 A 不是一个偶数呢？还是平分 A 一个数向上取整一个数向下取整吗？如果这样的话 A 是 15 之类的数上面的方法异或值不就很大了吗？

因为 \lfloor\frac{A}{2}\rfloor 相当于二进制中 A 右移一位，\lceil\frac{A}{2}\rceil 就相当于二进制中 A 右移一位再加 1，所以这两个数的前面有些位的数字是一样的，这样那些位的异或值就是 0。

那如果不一样的位呢？

我们让 a=\lfloor\frac{A}{2}\rfloor，b=\lceil\frac{A}{2}\rceil，设从前往后第 i 位数 a 与 b 不一样，可以证明 b 的第 i+1 位到最后一位都是 0，所以我们不管后面怎么微调 a\oplus b 的值都是这个定值，我太菜了不会证。

综上所述，我们可以让 a=\lfloor\frac{A}{2}\rfloor，b=\lceil\frac{A}{2}\rceil，这样为最优。

0x04

到这才讲这个确实有点唐了。

因为 a\oplus b\le a+b，所以我们可以让 a+b=a\oplus b，即让 a=X，b=0。

做个小结，以上四个小结论我命名为定值取值问题，是不是肥肠简单？

下面来讲一下给出三个数的范围 m，求三个数的异或最值情况下和最值的构造方法（两个数的读者自己推），可能需要读者的纸笔。

接下来直接令 a,b,c\in[0,m]，X=a\oplus b\oplus c，A=a+b+c，f(x) 与 g(x) 同上。

0x05

一上来就来了一个一眼题吗？

显然，如果 m 满足 m=f(m) 显然让 a=b=c=m 就行了。

读者可以自己写下一个二进制的 m 然后跟着下面给出的构造写出 X、a、b、c，需要按最后一位对齐。

先考虑 m<\frac{g(m)}{2}+g(m) 的情况。我们有 X=f(m)，a=m，b=m\oplus g(m)，c=f(m)\oplus g(m)。

是不是很神奇？我们来看看为什么这样取值是最优的。

首先要满足 X 最大，所以直接让 X=f(m)。

如果令 a=m，b 和 c 就是“异或值为定值，和最大”的问题，可参照上面的构造，首先若 a<g(m)，但因为 X=f(m) 的，所以肯定 b 或 c 其中一个大于等于 g(m) 的，所以我们可以让 b 或 c 与 a 交换，此时 a 还是 大于等于 g(m) 的。

但是为什么 a 一定要取到 m 呢？

因为我们先考虑只有两个数 a 与 b 的情况，此时 X=f(m)，所以 b=f(m)\oplus a，但是现在有 3 个数，相当于多了一个数，此时只要 b 有 0 的位，就可以让 b 和 c 的这个位都取 1，这样异或值没变，但是和变大了，所以我们只有两个数时让 b 的 0 位多一点，c 来的时候就能多加一点，又因为 b=f(m)\oplus a，只需要让 a 的 1 位多一点就行，但是又因为 a\ge g(m) 且 a\le m 的，所以就算你想 1 的位最多，a 也最多能取到 m。

否则，我们令 u 为 m 除去前导零的第一个零出现的位置前一位的值。

此时有 a=m，b=f(m)\oplus u，c=m\oplus u，显然 a,b,c\le m。

此时是最优的因为按照上面的方案 b 和 c 是取不到前面的第一位的，但是这个构造方案能让 b、c 取到首位且异或值不变，显然更优。

证完了，能理解吧？

0x06

同上，自己写数字，这个构造要进行特判，比较复杂。

的值。其中，\bigoplus 表示按位异或。

首先异或有 x\oplus x=0，所以我们想到抑或前缀和 sum，区间 [l,r] 的异或值就等于 sum_{l-1}\oplus sum_r。

考虑怎么统计答案，考虑固定右端点 r，统计 r 与以前的数的贡献，我们记前面的数中，在第 j 位有 x_{j,0} 个数是 0，x_{j,1} 个数是 1。

固定 r，第 j 位有贡献当且仅当 sum_{l-1} 的第 j 位异或 sum_r 的第 j 位为 1。

所以我们枚举 sum_r 的每一位 j，当这一位为 0 时，ans\gets ans+2^j\times x_{i,1}，当这一位为 1 时，ans\gets ans+2^j\times x_{i,0}，最后再累加 x_{i,0} 与 x_{i,1} 即可，时间复杂度 O(N\log V)，AC 记录。

ll n,a[N],sum[N],x[35][2],ans;
void solve() {
    cin >> n;
    rep(i,1,n) cin >> a[i],sum[i]=sum[i-1]^a[i];
    rep(i,0,n) rep(j,0,30) 
        if(sum[i]&(1<<j)) ans+=(1<<j)*x[j][0],x[j][1]++;
        else ans+=(1<<j)*x[j][1],x[j][0]++;
    cout << ans;
}

双倍经验多水一道题。

0x0a

再看这道题。

给出无向图 G，边 (A_i,B_i) 的权是 C_i，判断下列性质是否成立：

对于任意环，其边权的异或和是 0。

这道题非常水，甚至 1\le N,M\le 50 还有蓝……我们挑战 O(N+M)。

首先发现可以见一棵搜索树（DFS 生成树），此时有树边和返祖边，然后发现对于一个环，就是搜索树上的返祖边加这条返祖边到这个点的路径。

我们显然可以对搜索树进行一个树上前缀异或和，设为 x_i。对于每一条返祖边，设其连接 u 与 v，边权为 w，则 u 到 v 路径上的边权异或和为 x_u\oplus x_v，整个环（u 到 v 路径 + 返祖边）的异或和是 x_u\oplus x_v\oplus w，判断是否为 0 即可。

注意：图可能不连通，没有遍历所有连通块只有 80 分，别问我怎么知道的。

edge e;
int n,m,x[N],vis[N],ans;
void dfs(int u,int fa) {
    vis[u]=1;
    rept(e,u) {
        if(v==fa) continue;
        if(vis[v]==0) x[v]=x[u]^w,dfs(v,u);
        else ans&=(x[u]^x[v]^w)==0;
    }
}
void solve() {
    cin >> n >> m,ans=1,e.clr(n);
    rep(i,1,n) vis[i]=0,x[i]=0;
    rep(i,1,m) {
        int u,v,w;
        cin >> u >> v >> w;
        e.add(u,v,w),e.add(v,u,w);
    }
    rep(i,1,n) if(vis[i]==0) dfs(i,0);
    if(ans) cout << "Yes\n";
    else cout << "No\n";
}

0x0b

线性基也是构造，对吧？

线性基是一种擅长处理异或问题的数据结构。设值域为 [0,N]，就可以用一个长度为 \left\lceil\log N\right\rceil 的数组来描述一个线性基。

实质：多维向量的作为基底的特殊形式，可用高斯消元理解。

来说说线性基的几个性质。

• 线性基是原数组的极大线性无关组。所以线性基也就拥有一下性质：
  • 只含零向量的向量组没有极大无关组；
  • 只含零向量的向量组没有极大无关组；
  • 极大线性无关组对于每个向量组来说并不唯一，但是每个向量组的极大线性无关组都含有相同个数的向量；
  • 齐次方程组的解向量的极大无关组为基础解系。
  • 任意一个极大线性无关组都与向量组本身等价。
  • 一向量组的任意两个极大线性无关组都是等价的。
  • 若一个向量组中的每个向量都能用另一个向量组中的向量线性表出，则前者极大线性无关向量组的向量个数小于或等于后者。
• 线性基中每个元素只有唯一异或方案。
• 线性基的二进制最高位互不相同。
• 线性基的每一个的元素的最高位也是该元素在线性基的位次。
• 线性基的二进制最高位互不相同。
• 线性基中元素互相异或，异或集合不变。
• 如果线性基有 n 个元素，它的可异或的个数为 2^n-1。

接下来说说怎么构造线性基，Case 11 采用贪心法（更常用）。

我们考虑插入的操作，令插入的数为 x，考虑 x 的二进制最高位 j：

• 若线性基的第 i 位为 0，则直接在该位插入 x，退出；
• 若线性基的第 i 位已经有值 a_i，则 x=x\oplus a_i，重复以上操作直到 x=0。

如果退出时 x=0，则此时线性基已经可以表示原先的 x 了；反之，则为了表示 x，需要往线性基中加入一个新元素，显然时间复杂度为 \log V。

接下来证明一些东西。

求证：线性基中的所有非零向量线性无关。

证明：假设存在不全为零的系数 c_i 使得 \bigoplus^k_{i=0}c_iB_i=0。设 m 是最大的 i 满足 c_i\ne i，则：

B_m=\bigoplus^k_{i=0}c_iB_i

这与 B_m 的最高位是第 m 位矛盾，因为右边所有向量的第 m 位均为 0。

求证：原集合中每个数都能表示为线性基中若干向量的异或和。

证明：对于任意 x\in S，在插入过程中：

若 x 被存入 B_i，则 x 可直接表示。

若 x 被消为 0，则 x=\bigoplus B_i（过程中用的）

证明：贪心算法得到的异或和是最大的。

设最优解为 M，算法解为 A。从最高位开始比较：

若在某位 M 为 1 而 A 为 0：

该位必须由某个 B_i 贡献。

但算法一定会选择该 B_i，矛盾。

因此 A\ge M，又 M 是最优解，故 A=M。

以上证明来自这篇文章，感谢作者的贡献。

我们想想怎么算最大值。

显然，考虑异或最大值，从高到低遍历线性基。考虑到第 i 位时，如果当前的答案 ans 第 i 位为 0，就将 ans 异或上 a_i；否则不做任何操作。显然，每次操作后答案不会变小。

同样，我们考虑对于一个数 x，它与原数列中的数异或的最大值为多少。用与序列异或最大值类似的贪心即可解决。

想想最小值。

显然线性基中最小的数，设为 x，异或上线性基中其他的数都会变得更大，所以 x 为答案。

0x0c

上面说了怎么贪心构造线性基，接下来说说怎么高斯消元法构造线性基（不太常用）。

假设我们有一个序列 \{7,5,9,2\}，我们先把这四个数分别转化为二进制矩阵：

然后对这个矩阵进行高斯消元，消元步骤如下：

1. 从高到低位枚举。由于要通过二进制算数，我们尽量把位数从 0 开始从右往左以此递增。
2. 确定主元。假设枚举到了第 i 位，我们需要找到一个该位为 1 的数，将其移到确定的数的下方。
3. 对其他未确定的数：假如这个数第 i 位为 1，那就让这个数异或主元，让这一位变成 0。
4. 将这个数确定为线性基的数。

例如，上面的矩阵。

第一步，枚举位数 i=3（该位的值为 2^3）。确定 9 为主元，为了方便，把它换到第一行：

其他元素在这一位上全部为 0，所以不必异或，确定为线性基的数。

接下来枚举 i=2。由于第一个主元已经确定了，所以我们从后面的数选，找到主元 5，已经在第二行了，无需交换。

然后开始异或，元素 7 需要被主元元素 5 异或。得到：

确定主元 5 为线性基中的数：

接下来枚举 i=1。由于前两个主元已经确定了，所以我们从后面的数选，找到主元 2（原数是 7），已经在第三行了，无需交换。

然后开始异或，元素 2 需要被主元异或。得到：

确定主元 5 为线性基中的数：

接下来枚举 i=0。发现没有元素为主元，跳过。

枚举完成，最后线性基中元素为：

优点：高斯消元后的矩阵是一个行简化阶梯形矩阵。这意味着，给定一些数，选其中一些异或起来，求异或最大值，使用高斯消元法构造线性基后直接将线性基中所有元素都异或起来输出即可。

0x0d

刚刚学完线性基，拿道题练练手。

有 n 个数组 a_i，初始时每个元素为空，维护以下操作：

1. 1 x k 将 x 加入数组 a_k。
2. 2 l r 询问将数组 a_l,a_{l+1},\dots,a_r 中的元素任选任意个元素使得异或和最大。

这道题是单点修改区间查询，易得线段树维护。

现在需要维护两个线性基合并操作，我们记得线性基最多 \log V 个，所以只需要将其中一个线性基的每个元素都加到另一个线性基即可。

套一个树剖就可以双倍经验了。

0x0e

线性基一定要二进制吗？

实数线性基，我们要求的就是其中的一组基（如果一个物品可以通过其他的物品组合而成，那么它就不能是基的一部分）。

采用高斯消元即可。

后记

就先写到这了，求赞。

以后一定会更的，等我！