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

這里以非 $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啦……