a21*x1 XOR a22*x2 XOR ... XOR a2n*xn = b2

am1*x1 XOR am2*x2 XOR ... XOR amn*xn = bm
其中的所有a、b、x的值均為0或1。解異或方程組就是給出了所有的系數a和b之后，求出解（x1, x2 ... xn）。一般來說，題目的要求無非就是如下幾種：<1>求任意一組解；<2>求解的總數；<3>求出最優解（比如字典序最小的解或者加權以后權值最大/小的解等）。

（2）求解異或方程組的離線算法：
整體思想與普通方程組的高斯消元解法類似。
第一階段（消元）：設置一個變量p，一開始p=1，然后，i從1到n，每次執行：<1>若在第p個及以后的方程中，至少有一個方程的xi系數為1，設為第q個方程，則先將第p、q個方程交換，然后用第p個方程去XOR后面剩下的所有xi系數為1的方程（各系數包括b都對應進行XOR運算，實際上就是矩陣初等行變換），將它們的xi系數均變成0，最后p加1；<2>否則（第p個及以后的方程中xi系數均為0），xi是自由元（xi不管是取0還是1，都能導出整個方程組的一個解），按照自由元處理（隨便定值，然后將前面所有xi系數為1的方程全部代入xi的值XOR掉），p值不變。(感謝HN SYJ神犇，在總結中講到了如果遇到自由元的話p值是不能變的，否則會疵，見這里）
第二階段（回代求解）：在第一階段結束后，若出現了S個自由元，則會在整個方程組的最后出現S個多余方程，它們的等號左邊所有系數均為0（顯然值也為0）。對于這些多余方程，如果有等號右邊為1的，則整個方程組無解。否則，如果所有多余方程的等號右邊均為0，則整個方程組有2^S個解（因為S個自由元可以隨便取值，都能導出解）。如果要求具體的解，則從第(m-S)個方程開始，往回代，設立變量p，初始p=m-S，逆序枚舉每個未知數（自由元除外），對于未知數xi，可以從第p個方程中直接得到其值（因為此時第p個方程等號左邊必然只有xi系數為1，等號右邊是幾，xi值就是幾），然后，將之前的所有xi系數為1的方程全部用第p個方程XOR掉，p--。
具體實現的時候有一些技巧：
1)在第一階段第<1>步XOR的時候，實際上只要枚舉xi及其后面的未知數就行了，因為前面的未知數已經消掉了；在第<2>步XOR的時候，只需要xi和等號右邊的系數b，因為其它的系數均為0；
2)第一階段的p可以直接留到第二階段繼續用，只不過要減1。

（3）求解異或方程組的在線算法：
這里的在線算法其實指的是，它可以隨時在后面增加新的方程，直接擴展已求出的解以及更新解的總數，而不用每次重新求解。這個算法在某些求”XOR值最大“的問題中顯然比較有用。
為了講清楚這個算法，首先要引入”關鍵元“：在消元過程中，每個方程有至多一個”關鍵元“，它決定了該方程可以去XOR后面的哪種方程。設C[i]為關鍵元為xi的方程編號，若C[i]==-1（以xi為關鍵元的方程不存在），則xi為自由元，反之亦然。一開始，所有的C值均為-1。
在新加入一個方程時，i從1到n枚舉，若該方程xi系數為1，則看一下C[i]是否為-1，若為-1，則xi為該方程關鍵元，C[i]設為該方程編號，結束（此時，xi不再是自由元，因此整個方程組解的總數減半）；若不為-1，則用編號C[i]的方程去XOR該方程（其實只要XOR xi及其之后的部分），將該方程中的xi消去。如果最終i枚舉到n時仍然木有找到關鍵元，則該方程無關鍵元，也就是說該方程是一個多余方程（0=0或0=1），如果是0=0，則不影響解的總數，如果是0=1，則整個方程組無解了。
如果要求具體的解，則與離線算法的第二階段類似，只是回代求解時，p不能再是逆序的了，而應該是每個C[i]的值。此外，對于C[i]==-1的（即xi是自由元），隨便定值，并代到所有方程中XOR掉它。

顯然，以上兩種算法的時間復雜度均為O(n²m)。

（4）算法常數優化——壓位：
在具體實現的時候，需要用一個bool矩陣A[m][n+1]來存儲所有的系數（a、b），這樣很浪費，因為完全可以用一個int矩陣，一下存儲32位。這種壓位思想可以帶來常數上的優化，因為在用一個方程去XOR另一個時，時間將變為原來的1/32。
實現起來比不壓位的要麻煩一些。具體來說，首先，調用原矩陣的第i行第j列是否為1需要寫成A[i][j/32] & (1 << (j % 32))（原矩陣第i行第j列為0當且僅當該值為0），對于等號右邊的b系數，在原矩陣中為第n列，因此寫成A[i][n/32] & (1 << (n % 32))。在實現過程中，為了避免重復計算，可以設n0=n/32，q=n%32，q0=j/32，q1=j%32，n0和q預先算出，在枚舉j（未知數編號）時維護q0、q1。
另外需要嚴重注意的是：在求出了某個未知數xi的值之后代入到其它方程中時，如果是單個代入不整體XOR，則i和n列都要處理，但如果是整體XOR，則要特判一下i和n列在壓位之后是否壓到同一位里了，若壓到同一位里則只能XOR一次！！！！！！！！！
（其實是可以壓64位的，但由于long long的常數較大且在求1<<q時還要強制類型轉換，所以得不償失，不如壓32位快）

例題：JSOI2012 arc
建模方法：設一組解(x1, x2 ... xn)為：xi==0當且僅當i在上游。對于原圖中給出的有向圖，若i的出度為偶數，則需要滿足i指向的那些點的x值XOR之和為0即可（不管xi是0還是1）；若i的出度為奇數，則需要滿足i及其指向的那些點的x值的XOR之和為1即可（不管xi是0還是1）。這樣就轉化為求異或方程組的特解問題，假設在求解過程中，對于所有的自由元均定為0。
代碼（均為壓位之后的）：
離線算法：
在線算法：