Mato is No.1

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。解異或方程組就是給出了所有的系數(shù)a和b之后，求出解（x1, x2 ... xn）。一般來說，題目的要求無非就是如下幾種：<1>求任意一組解；<2>求解的總數(shù)；<3>求出最優(yōu)解（比如字典序最小的解或者加權(quán)以后權(quán)值最大/小的解等）。

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

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

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

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

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