线性基

原集合的每一个数都能被线性基的数异或和表示。

线性基的每一位的数最高位 $1$ 不同。

void insert (ll x) {
	for (int i = 60; i >= 0; i--)
		if((x >> i) & 1)
			if(!a[i]) {a[i] = x; return;}
			else x ^= a[i]; 
}

极小线性基重建，

void rebuild() {
	cnt = 0;
	for (int i = 60; i >= 0; i--)
		for (int j = i - 1; j >= 0; j--)
			if((a[i] >> j) & 1) a[i] ^= a[j];
	for (int i = 0; i <= 60; i++) if(a[i]) b[cnt++]=a[i];
}

有关线性基的一切运算都可以看做矩阵的初等行列变换，也就可以将其看做线性规划问题。同样，可以离线使用高斯消元来构造极小线性基。

这些性质。

高斯消元

吃老本

给定一个线性方程组，对其求解。

假设我们要求解一个线性方程组：

$$\left\{\begin{matrix} x&+& 3y&+& 4z&=&5 \\ x&+& 4y&+& 7z&=&3 \\ 9x&+& 3y&+& 2z&=&2 \end{matrix}\right.$$

按照数学课上常规操作，我们应该先选择一个式子的 $x$ ，用它消去其它式子的所有的 $x$ ，剩下的式子就可以看作是一个 $(n-1)$ 元一次方程了，接下来即可递归下去，直到最后一元 $z$ ，就能代回到其它式子得到答案了。

比如上面的式子先用第三个式子消掉其它的 $x$ ：

$$\left\{\begin{matrix} 0\times x&+& \frac{8}{3}y&+& \frac{34}{9}z&=&\frac{43}{9} \\ 0\times x&+& \frac{11}{3}y&+& \frac{61}{9}z&=&\frac{25}{9} \\ 9x&+& 3y&+& 2z&=&2 \end{matrix}\right.$$

剩下的式子，再用第二个式子消 $y$ ：

$$\left\{\begin{matrix} 0\times y&+& (-\frac{114}{99}z)&=&\frac{273}{99} \\ \frac{11}{3}y&+& \frac{61}{9}z&=&\frac{25}{9} \\ \end{matrix}\right.$$

得到 $z=-2.39$ ，用 $z$ 代回得到 $y=5.18,x=-0.97$ 。

在代码中实现就是这样的步骤。

	for (int i = 1; i <= n; i++) {
		int mxi = i;
		for (int j = i + 1; j <= n; j++)
			if(fabs(a[mxi][i]) < fabs(a[j][i])) mxi = j;
		if(fabs(a[mxi][i]) < 1e-7) {
			puts("No Solution"); return 0;
		}
		swap(a[mxi], a[i]);
		double inv = a[i][i];
		for (int j = i; j <= n + 1; j++) a[i][j] /= inv;
		for (int j = i + 1; j <= n; j++) {
			inv = a[j][i];
			for (int k = i; k <= n + 1; k++) a[j][k] -= a[i][k] * inv;
		}
	} 
	ans[n] = a[n][n + 1];
	for (int i = n - 1; i; --i) {
		ans[i] = a[i][n + 1];
		for (int j = i + 1; j <= n; ++j)
			ans[i] -= ans[j] * a[i][j];
	}