線性基是一個奇妙的集合（我摘的原話）

這里以非 $OI$ 的角度介紹了線性基

基礎部分

模板題

給你 $n$ 個數的集合，讓你選出任意多個不重復的數，使得它們的異或和最大。

線性基是什么

我們稱集合 $B$ 是集合 $S$ 的線性基，當且僅當 集合 $B$ 和 集合 $S$ 的元素數相同，且集合 $B$ $=$ 集合 $S$ 能異或出的數的集合。

其中“能異或出的數的集合”表示從集合中選出任意多個數（不能不選），它們的異或和組成的集合。

怎么構造線性基

異或是基于二進制的，我們當然要以二進制位的角度考慮啦！

我們依次插入每個給定集合 $S$ 的數，設我們要往集合 $B$ 中插入一個集合 $S$ 的數 $x$，我們將 $x$ 從高往低位遍歷二進制位。

設當前遍歷到第 $i$ 位，

若遇到 $1$，則判斷之前是否已插入過最高位為 $1$ 的數（設其為 $p_i$）：

? ? ? ?- 如果插入過，就把當前要插入的數異或上 $p_i$，再往低位遍歷；

? ? ? ?- 如果沒插入過，就把當前插入的數賦給 $p_i$，退出。

可以通過數學歸納法（從 $p_i$ 和從高到低位消 $1$ 兩個角度）證明，這樣構造使 $p_i$ 的值的最高二進制位是第 $i$ 位（這一位當然就是 $1$ 了）。

對于“$p_i$ 的值的最高二進制位是第 $i$ 位”這部分，一開始 $p$ 數組都未被賦過值，滿足定義；然后如果另一部分是正確的，那賦值之后 $p$ 數組依然滿足定義。

對于“從高到低位消 $1$”這部分，如果另一部分是正確的，每次異或 $p_i$ 都不會對更高位造成影響（那些位還是 $0$），第 $i$ 位會被消成 $0$，所以只有更低位可能有 $1$，往下遍歷就行了。

已經說過，一開始 $p$ 數組滿足定義，所以第一部分正確，然后兩部分互相歸納下去即可完成證明。

?

我們把這個數組 $p$ 稱作“有序的”集合 $B$ 吧！（因為集合本身有無序性）

據說這種構造方式很像高斯消元？這個還不是，下文會說怎么構造才是。

這樣構造的意義是什么

對于集合 $S$ 中的任意兩個數 $x,y$，它們能異或出的三種數是（假設不能一個都不取，即不取空集）$x,y,x\bigoplus y$。

由于異或的偶數抵消（即偶數個相同的數相異或等于 $0$，比如 $x\bigoplus (x\bigoplus y) = y$）性質，我們可以把 $x$ 和 $y$ 的任意一個換成 $x\bigoplus y$，這兩個數能異或出的三種數依然是 $x,y,x\bigoplus y$。

拓展：把兩個 $S$ 的子集中的數任意互相異或，再把兩個子集合并得到的子集 能異或出的數的集合 $B_1$ 與把任意互相異或之前的子集合并得到的子集 能異或出的數的集合 $B_2$ 相等。

重要結論：所以我們把原集合 $S$ 中的數任意互相異或，集合 $S$ 能異或出的數的集合 $B$ 不變。

由于我們構造線性基的方式中，每個 $p_i$ 都是原集合 $S$ 中若干個數的異或和，所以集合 $p$ 能異或出的數的集合 與原集合 $S$ 能異或出的數的集合相等。

?

那為什么要把要插入的數 $x$ 不斷異或 $p_i$？

對于一個新插入線性基的數，根據前述構造方式，如果從高到低遍歷完所有二進制位，都沒能插入給一個 $p_i$，那這個數必定被異或成了 $0$。

證明：

? ? ? ?- 從高到低遍歷到第 $i$ 個二進制位時，只有當前要插入的數 $x$ 的第 $i$ 位為 $1$ 時才會考慮異或 $p_i$。

? ? ? ?- $p_i$ 的值的最高二進制位就是第 $i$ 位（之前證明過），且這一位為 $1$。

? ? ? ?結合這兩條，我們發現，要插入的數 $x$ 一定會被從高到低位依次被異或成 $0$，而且已經遍歷過的高位不會再被異或成 $1$。

? ? ? ?在遍歷最高位時，這個性質是成立的，而往低位遍歷時，可以結合上述兩條，用數學歸納法證明。

所以，遍歷完所有位之后，如果 $x$ 還沒被插入，就肯定被一堆 $p_i$ 異或成 $0$ 了。

這是什么意思呢？

說明 $x$ 一開始的值（就是在集合 $S$ 中的值）是能通過其它若干個數異或出來的（之前說過，$p_i$ 都是原集合 $S$ 的若干個數的異或和）。

那就已經能被表示了，所以不要它了。

?

綜上，可以看出這個線性基最叼的地方是：它能把原集合構造成元素很少的新集合，使其能異或出的數的集合不變，且新集合能容納一些特殊性質。

那模板題怎么做

我們發現，在線性基中，每種最高位的數只有一個（一個 $p_i$ 對應一個最高位）。構造完線性基后，我們從高往低再遍歷一次二進制位，做貪心（因為高位的一個 $1$ 比低位的任意多個 $1$ 都大）。

具體地說，就是設當前最大值變量為 $ans$，初始時使 $ans$ 為 $0$，從高往低遍歷到第 $i$ 位時，如果 $ans\bigoplus p_i\gt ans$，就更新 $ans$ 為 $ans\bigoplus p_i$。

證明：可以這樣考慮，遍歷到第 $i$ 位時，比第 $i$ 位高的位都已經極大，然后我們現在要確保第 $i$ 位極大。結合數學歸納法可知，高位優先大的貪心策略能保證答案最大。

?

拓展部分

請確保基礎部分都會了再看這部分

首先說一個線性基特別重要的性質：一個線性基能異或出的每個數的組成方案是唯一的。換句話說就是對于一個線性基的任意兩個不同的取數方案，異或出的數兩兩不相等。

原因很簡單，根據之前說過的構造方法，如果新插入的一個數能被線性基中已有的數表示出來，那它在遍歷完所有二進制位后也不會被插入，且它一定被若干個 $p_i$ 異或成 $0$。

由此可以推出 $2$ 個性質：

? ? ? ?- 線性基能異或出的數一定不包括 $0$（包括 $0$ 說明線性基中有兩個相等的數，其中一個就能被另一個表示了，不符合構造要求；而且線性基中每種最高位的數只能有一個，顯然兩個相等的數的最高位也是相等的，也不符合構造要求）

? ? ? ?- 假設線性基中有 $cnt$ 個數，線性基能異或出的數的集合大小為 $2^{cnt}-1$（$-1$ 就是去掉一個數都不取的情況）

（這些概念是給你深入學習用的，可能會有用）

模板題加強版

給你 $n$ 個數的集合，讓你選出任意多個不重復的數，使得它們的異或和再異或一個常量 $s$ 最大。

題解

做之前的模板題時，我們讓 $ans$ 一開始為 $0$。

這是為什么？

由于異或的性質，一個數異或 $0$ 等于這個數本身，所以我們可以把之前的模板題看做 要求若干個數的異或和再異或一個常量 $0$ 最大。

又因為異或有交換律，所以我們可以交換順序，讀作“要求一個常量 $0$ 異或若干個數的異或和最大”。

這道題同理。所以讓 $ans$ 一開始為 $s$，再跟之前的模板題一樣做最大值貪心就行了。

（這是我自己想出來的解釋，好像沒那么嚴謹）

XOR （HDU3949）

給你 $n$ 個數的集合，讓你選出任意多個不重復的數（至少選一個），把它們的異或和放入一個新集合中（集合是有互異性的，相同的數只保留一個），求新集合的第 $k$ 小值。

簡化題意：求線性基能異或出的數的集合的第 $k$ 小（其實某些情況下是 $k-1$，后面會說）。

題解

首先，對于這道題，線性基的構造方式就跟之前不太一樣了，因為之前只要求最大，而現在要求第 $k$ 小。

但我們知道，線性基是以每個二進制為最高位存一個數的，那是不是容易想到把 $k$ 進制分解呢？

這樣的話，在前文的構造方式的基礎上，我們只需要改點限制：規定 $p_i$ 的值的最高位是第 $i$ 位，且在此基礎上 $p_i$ 最小。

直接加了一個最小的限制，這怎么做？

考慮之前的 $p_i$，它除了在第 $i$ 位有個 $1$ 外，在更低的位還有若干個 $1$。

那我們是否可以用線性基中的某些數，盡量消去低位的那些 $1$？（我們知道，線性基中的數都是原集合 $S$ 的若干個數的異或和，線性基中兩個數的異或和還是原集合 $S$ 的若干個數的異或和）

這個很好做，往線性基插入一個新數時，用這個 $p_i$ 更新 $p$ 數組的其它所有值就行了。

詳細做法：

　　- 對于低位

　　　　現在插入的一個數放到了 $p_i$，它在一個更低的二進制位（設其為第 $j$ 位）上為 $1$，且 $p_j$ 已被賦過值，那就把 $p_i$ 更新為 $p_i\bigoplus p_j$。

　　　　證明：這種情況下讓 $p_i$ 異或 $p_j$，不會對比第 $j$ 位更高的位造成影響，但會使 $p_i$ 的第 $j$ 位變成 $0$，這種情況下即使更低的位異或出再多的 $1$，這個數總體也變小了。

　　　　為了方便，從大到小枚舉 $j$ 即可。

　　- 對于高位

　　　　只考慮低位顯然不對，因為有可能 $p_i$ 的第 $j$ 個二進制位為 $1$，而 $p_j$ 此時可能沒有值，但它以后被賦了值，這種情況下也應該用 $p_j$ 更新 $p_i$。

　　　　我們只能用賦值晚的更新賦值早的，所以對于插入的一個數 $p_i$，不僅要用更低位的 $p_j$ 更新它，還要用它更新更高位的 $p_j$。

　　　　這一部分依然從大到小枚舉 $j$。

這樣就把線性基中的所有數都互相更新成滿足限制的最小值，具體見代碼吧（反正很短）。

其實這才是線性基的通用構造方式（比如對于模板題，多出來的要求對答案沒有影響，因此該構造方案可以兼容使用）。另外說一下，換個角度看這個構造方式，其實就是標準的高斯消元+矩陣消成三角形，文章開頭給了個非 $OI$ 角度介紹線性基的鏈接，可以去那里看看矩陣高斯消元的講解。那里所謂的把不在對角線上的 $1$ 能消掉就消掉，其實也就是讓每行的數最小。異曲同工吧？

?

如上改變線性基的構造方式后，把 $k-1$ 二進制分解，若第 $i$ 位為 $1$ 就把 $ans$ 異或上 $p_i$。

證明比較冗雜（其實是不會表達），這里盡量短地說一下（其實還是很長）：

你會發現，若 $p_i$ 的第 $j$ 個二進制位是 $1$，那 $p_j$ 一定沒被賦過值（如果有值就能更新 $p_i$ 使其更小了）。

所以所有的 $p_i$ 在各自的位數范圍內（就是不超過最高位）都必須且只能在某些相同的位上有 $1$。

比如線性基里的三個數（二進制表示）可能是這樣的（高位自動補成 $0$，用于對齊，其實不用考慮）：$$111\space\space 011\space\space?001$$

而不可能是這樣的：$$111\space\space 010\space\space 001$$

因為最低位要么都是 $1$，要么都是 $0$（也就是說要么最低位的 $p_i$ 有值，要么沒值，不能模棱兩可）。

這樣的話，有一個煩人的顧慮就沒了。

這個顧慮我不知道怎么叫名字……

大概就是說，如果 $p_i$ 表示線性基中最高位二進制位為 $i$ 的數，我們知道第 $2^{i-1}$ 大異或和為 $p_i$，第 $2^{j-1}$ 大異或和為 $p_j$，但 $p_i\bigoplus p_j$ 不一定是第 $2^{i-1}+2^{j-1}$ 大異或和（如果直接是的話，證明早就結束了）。

因為兩數異或后第 $i$ 到 $j-1$ 位的數是不用爭議的達到最小了（因為只有 $p_i$ 有那些位），但第 $j$ 位及以后的位根本沒有保證啊！

為了解決這些顧慮，我們拆開考慮：

對于第 $j$ 位，$p_i$ 的第 $j$ 位必定是 $0$，因為 $p_j$ 被賦過值。

對于更低的位，$p_i$ 和 $p_j$ 在那些位上的數完全相同，即一位要么都是 $1$，要么都是 $0$。

由于我們前面的新構造方式 是考慮把每個 $p_i$ 的 $1$ 消成 $0$，因此如果我們想得到其它的異或和，只能不消 $p_i$ 的 $1$，也就是把一些 $0$ 改回 $1$。

顯然，只有 $p_i$ 為 $1$ 的位才有可能在與其它若干個 $p_j$ 異或后得 $1$（異或奇數次），而 $p_i$ 為 $0$ 的位在異或后，這一位肯定還是 $0$（因為異或的那些 $p_i$ 在同位也必須是 $0$）。

保留 $p_i$ 原有的 $1$，而再把 $0$ 改成 $1$，$p_i$ 在與其它若干個 $p_j$ 的異或和 只可能在把原異或和（就是把 $p_i$ 的 $0$ 改成 $1$ 之前與這些 $p_j$ 的異或和）的某些二進制位由 $0$ 變成 $1$，新的異或和顯然不會變小。

所以顧慮就解決了，?$p_i\bigoplus p_j$ 在第 $j$ 位及更低位的部分的數 已經達到最小，結合二進制原理可得 $p_i\bigoplus p_j$ 是第?$2^{i-1}+2^{j-1}$ 大異或和。

?

做完了？

然而這道題還有個比較坑的地方……

就是它要求至少選一個數，也就是不能不選（這種情況下異或和為 $0$），但你可以選出若干個數（至少一個）的異或和為 $0$（這種情況下 $0$ 才是最小的異或和），然而線性基中的數并不能異或出 $0$（因為任意兩個數的最高位都不相同，至少最大的那個數的高位就消不掉），所以我們要特判能否異或出 $0$。

這個也很好判，回顧一下線性基的構造：你在往線性基中插數的時候，如果最終這個數沒被插入，那它一定就被異或成 $0$ 了。這說明原集合 $S$ 的若干個數（至少一個）能異或出 $0$，這時把 $k$ 改為 $k-1$ 即可。

Xor（WC2011 / bzoj2115）

給定一個 $n(n\le 50000)$?個點 $m(m\le 10000)$?條邊的無向圖，每條邊上有一個權值。請你求一條從?$1$ 到?$n$ 的路徑，使得路徑上的邊的異或和最大。

路徑可以重復經過某些點或邊，當一條邊在路徑中出現了多次時，其權值在計算異或和時也要被計算相應多的次數。

注意：這條路徑可以多次經過 $1$ 和 $n$，只要路徑的第一個點是 $1$ 且最后一個點是 $n$ 即可。

可能有重邊、自環。

題解

其實這題的重點是圖論找性質……

如果路徑不可以重復經過點邊，那這就是我們常見的簡單路徑了，直著從起點連到終點的那一種。

如果路徑可以重復經過點邊，簡單路徑本身不會變（因為你肯定要從起點走到終點），變的只是可以多走一些環。

容易發現，一條可以重復經過點邊的路徑的異或和 相當于一條從起點到終點的簡單路徑的異或和 異或 若干個（可以是 $0$ 個）任意的環的異或和。

哪里來的若干個任意的環？

思考一下，從簡單路徑上的任意一點出發，到達一個環，跑一圈，再原路返回，從簡單路徑上的點到那個環的往返路徑走了兩次，異或和抵消為 $0$，因此實際上就多了一圈環的異或和。

那可不可以去跑一圈環套環（或者多個環套起來）呢？也是可以的。這樣的話每個環依然都恰好被跑了一次，異或和就是 這些環上所有邊權的異或和相異或。

由此也很容易看出，每個環至多只需要考慮跑一次（即算一次異或和）。因為跑偶數次的話，環的異或和會被抵消為 $0$，因此多就是算一次環的異或和，那跟跑一圈一樣。

?

所以把圖中的所有環提出來（$DFS$ 根據生成樹的返祖邊找環），記下每個環上所有邊權的異或和。

然后枚舉每條簡單路徑，求出該簡單路徑的異或和（設其為 $s$），問題變成了找若干個環，使這些環的異或和相異或 再異或 $s$ 最大。這就是前文講過的模板題加強版了。

這真的是很好的思維題啊！

Shallot（bzoj4184）

有一個一開始為空的集合，支持三種操作：加入一個數，刪除一個數；每次完成前兩種操作中的任意一個后，回答當前集合中若干個數的異或和最大是多少。

題解

動態線性基？麻麻我要離線

容易發現，線性基不支持刪除……（想一想就知道了）

但可以離線，那線段樹分治每個數出現的時間就行了（標記永久化），于是成了不用刪除操作的裸題。

時間復雜度 $O(31\times n\times log(n))$。

albus就是要第一個出場

給定 $n(n\le 10000)$ 個數 $a_1, a_2, \ldots, a_n$，以及一個數 $Q$。將 $a_1, a_2, \ldots, a_n$ 的所有子集（可以為空）的異或值從小到大排序得到序列 $B$，請問 $Q$ 在 $B$ 中第一次出現的下標是多少？保證 $Q$ 在 $B$ 中出現。

題解

我靠結論題

我當我在學習

?

這題最關鍵的問題就是異或和不去重！

我們知道，線性基每種選數方案的異或和是互不相同的（前文證明過該結論）。

那我們考慮一下每個數出現了多少次。

不難想到，線性基里的數很少，那沒插入線性基的那些數是怎么著來著？

沒錯，就是被線性基中若干個數異或成 $0$ 后扔掉了。也就是那些數已經能被線性基中的數異或出來了。

如果我們不扔掉這些數，把這些 $0$ 也插入線性基，那異或和會是什么情況？

就是隨便用這些 $0$！

假設原集合給了 $n$ 個數，線性基大小為 $|B|$，那剩下的 $n-|B|$ 個數肯定就是這些 $0$ 了。

在放入這些 $0$ 之前，線性基的每種選數方案異或出了一個唯一的異或和（也就是只有這一種方案得到這個異或和），現在多了 $n-|B|$ 個 $0$，而每個 $0$ 都可以用或不用，總共就有 $2^{n-|B|}$ 種方案得到這個異或和。

?

之前講過了求第 $k$ 小的方法，現在我們要找比一個數 $Q$ 小的異或和的數量，本來是二分，但由于是在二進制位上做，所以可以優化為 只要在原線性基中枚舉每個 $p_i$，嘗試一下把 $sum$ 異或上 $p_i$ 是否小于 $Q$，如果小于就異或上這個數就行了，順便加上比這個數小的數的數量（就是 $2^i$）。最后別忘了答案 $+1$（因為問的是 $Q$ 本身的出現位置，要算上自己的排名，剛才統計的只是比它小的數的數量）。

做完這道題后才發現，原來隨便給一堆數，每個能異或出的數的出現次數都相同？我fo啦……

后記

1. 線性基不資瓷刪除

2. 線性基大小為所有數的最大二進制位數（這不是廢話么）

3. 線性基（大概）不資瓷限定選數的數量

4. 怎么什么數學內容都能硬套到 $OI$ 中……

在美妙的數學王國中暢游

轉載于:https://www.cnblogs.com/scx2015noip-as-php/p/linear_basic.html

總結

以上是生活随笔為你收集整理的【基础操作】线性基详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。