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

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

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

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

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