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。解异或方程组就是给出了所有的系数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。
代码（均为压位之后的）：
离线算法：
在线算法：