高斯消元（模板及bitset优化异或方程）

模板

int nw = 1; // 处理到第几行
for (int i = 1; i <= n; i ++ ) // 枚举第i列（同一个主元）
{
    int pos = nw;
    for (int j = nw + 1; j <= n; j ++ ) if (fabs(a[j][i]) > fabs(a[pos][i])) pos = j; // 找到系数最大的一项，尽可能防止除0
    if (a[pos][i] == 0) continue; // 这一列全是0，可能多解，也可能无解
    for (int j = 1; j <= n + 1; j ++ ) swap(a[nw][j], a[pos][j]);
    for (int j = 1; j <= n; j ++ )
    {
        if (nw == j) continue;
        ld tmp = a[j][i] / a[nw][i]; // 用第nw行消第$j$行
        for (int k = i + 1; k <= n + 1; k ++ ) a[j][k] -= a[nw][k] * tmp; // 枚举列
    }
    nw ++ ;
}
if (nw < n + 1)
{
    while (nw < n + 1) if (a[nw ++ ][n + 1] != 0) {puts("-1"); return 0;} // 无解
    puts("0"); return 0; // 无数解
}

异或方程组

for (int i = 1; i <= n; i ++ )
{
	if (!a[i][i])
    {
		for (int j = i + 1; j <= n; j ++ )
		{
			if (a[j][i])
			{
				swap(a[i], a[j]);
				break;
			}
		}
	}
    if (!a[i][i]) r ++ ; // 自由元，即这个变量可以随意取0/1
    for (int j = 1; j <= n; j ++ ) if (a[j][i] && j != i) a[j] ^= a[i];
}

要讲一下(a[x][y])是如何构造的。

其实就是按照题目的意思来。比如某题要求

[displaystyleleft(igoplus_{e(u,v)in E}l_v ight)oplus l_u=1(l_u=0/1) ]

那么对于每个(x)，首先(a[x][x]=1)（考虑自己），然后(forall{e(x,y)in{E}},a[x][y]=1)（考虑(y)）。最后，(a[x][n+1]=1)（(a[x][n+1])存的是第(x)个方程的答案）

注意到有些异或方程要求最优解，但有一些自由元，就可以(dfs)，爆枚这些自由元的取值，更新答案。