a11*x1 XOR a12*x2 XOR ... XOR a1n*xn = b1
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
2m)。
（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。
代碼（均為壓位之后的）：
離線算法：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 2005, KS = 32, MAXN0 = (MAXN + 1) / KS + 1, INF = ~0U >> 2;
int n, n0, q, A[MAXN][MAXN0];
bool res[MAXN], res_ex = 1;
void init()
{
freopen("arc.in", "r", stdin);
int q0 = 0, q1 = 0, x, y;
scanf("%d", &n); n0 = n / KS; q = n % KS;
re(i, n) {
scanf("%d", &x);
if (x & 1) {A[i][q0] |= 1 << q1; A[i][n0] |= 1 << q;}
re(j, x) {scanf("%d", &y); y--; A[i][y / KS] |= 1 << (y % KS);}
if (q1 == KS - 1) {q0++; q1 = 0;} else q1++;
}
fclose(stdin);
}
void solve()
{
int q0 = 0, q1 = 0, p = 0, x;
ll tmp;
re(i, n) {
x = -1;
re2(j, p, n) if (A[j][q0] & (1 << q1)) {x = j; break;}
if (x >= 0) {
if (x != p) {re3(k, q0, n0) {tmp = A[x][k]; A[x][k] = A[p][k]; A[p][k] = tmp;}}
re2(j, p+1, n) if (A[j][q0] & (1 << q1)) re3(k, q0, n0) A[j][k] ^= A[p][k];
p++;
} else {
res[i] = 1;
re(j, p) if (A[j][q0] & (1 << q1)) {A[j][q0] &= ~(1 << q1); A[j][n0] ^= 1 << q;}
}
if (q1 == KS - 1) {q0++; q1 = 0;} else q1++;
}
re2(i, p, n) if (A[i][n0] & (1 << q)) {res_ex = 0; return;} p--;
rre(i, n) {
if (q1) q1--; else {q0--; q1 = KS - 1;}
if (!res[i]) {
res[i] = A[p][n0] & (1 << q);
re(j, p) if (A[j][q0] & (1 << q1)) {
A[j][q0] ^= A[p][q0]; if (q0 < n0) A[j][n0] ^= A[p][n0];
}
p--;
}
}
}
void pri()
{
freopen("arc.out", "w", stdout);
if (res_ex) {
int sum = 0; bool SPC = 0;
re(i, n) if (!res[i]) sum++;
printf("%d\n", sum);
re(i, n) if (!res[i]) {
if (SPC) putchar(' '); else SPC = 1;
printf("%d", i + 1);
}
puts("");
} else puts("Impossible");
fclose(stdout);
}
int main()
{
init();
solve();
pri();
return 0;
}
在線算法：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 2005, KS = 32, MAXN0 = (MAXN + 1) / KS + 1, INF = ~0U >> 2;
int n, n0, q, A[MAXN][MAXN0], B[MAXN];
bool C[MAXN], res[MAXN], res_ex = 1;
void init()
{
freopen("arc.in", "r", stdin);
int q0 = 0, q1 = 0, x, y, _q0, _q1;
scanf("%d", &n); n0 = n / KS; q = n % KS;
re(i, n) {
scanf("%d", &x);
if (x & 1) {A[i][q0] |= 1 << q1; A[i][n0] |= 1 << q;}
re(j, x) {
scanf("%d", &y); y--; _q0 = y / KS; _q1 = y % KS;
A[i][_q0] |= 1 << _q1;
}
if (q1 == KS - 1) {q0++; q1 = 0;} else q1++;
}
fclose(stdin);
}
void solve()
{
re(i, n) B[i] = -1;
int q0, q1, x;
re(i, n) {
q0 = q1 = 0;
re(j, n) {
if (A[i][q0] & (1 << q1)) {
x = B[j];
if (x == -1) {B[j] = i; break;} else re3(k, q0, n0) A[i][k] ^= A[x][k];
}
if (q1 == KS - 1) {q0++; q1 = 0;} else q1++;
}
}
q0 = n0; q1 = q;
rre(i, n) {
if (q1) q1--; else {q0--; q1 = KS - 1;}
if ((x = B[i]) >= 0) {
res[i] = A[x][n0] & (1 << q);
re(j, n) if (j != x && (A[j][q0] & (1 << q1))) {
A[j][q0] ^= A[x][q0]; if (q0 < n0) A[j][n0] ^= A[x][n0];
}
} else {
res[i] = 1;
re(j, n) if (A[j][q0] & (1 << q1)) {
A[j][q0] &= ~(1 << q1); A[j][n0] ^= 1 << q;
}
}
}
re(i, n) if ((x = B[i]) >= 0) C[x] = 1;
re(i, n) if (!C[i] && (A[i][n0] & (1 << q))) {res_ex = 0; return;}
}
void pri()
{
freopen("arc.out", "w", stdout);
if (res_ex) {
int sum = 0; bool SPC = 0; re(i, n) if (!res[i]) sum++;
printf("%d\n", sum);
re(i, n) if (!res[i]) {
if (SPC) putchar(' '); else SPC = 1;
printf("%d", i + 1);
}
puts("");
} else puts("Impossible");
fclose(stdout);
}
int main()
{
init();
solve();
pri();
return 0;
}