矩阵

struct Matrix
{
	static int n; //方阵代替矩阵
	ll a[N][N];
	Matrix(ll k = 0)
	{
		for (int i = 0; i < n; ++i)
			fill(a[i], a[i] + n, 0), a[i][i] = k;
	}
	friend Matrix operator*(const Matrix &a, const Matrix &b)
	{
		Matrix r(0);
		for (int i = 0; i < r.n; ++i)
			for (int j = 0; j < r.n; ++j)
				for (int k = 0; k < r.n; ++k)
					r.a[i][j] = M.add(r.a[i][j], M.mul(a.a[i][k], b.a[k][j]));
		return r;
	}
	friend Matrix pow(Matrix a, ll b)
	{
		Matrix r(1);
		for (; b; b >>= 1, a = a * a)
			if (b & 1)
				r = r * a;
		return r;
	}
	friend ll det(Matrix a) //矩阵a的n阶行列式
	{
		ll ans = 1;
		for (int i = 0; i < a.n; ++i)
		{
			for (int j = i + 1; j < a.n; ++j)
				while (fabs(a[j][i]) > EPS)
				{
					ll t = a[i][i] / a[j][i];
					for (int k = i; k < n; ++k)
						a[i][k] -= t * a[j][k], swap(a[i][k], a[j][k]);
				}
			if (fabs(ans *= a[i][i]) < EPS)
				return 0;
		}
		return ans;
	}
};
//int Matrix::n=N;

高斯消元

struct GaussElimination : Matrix
{
	void ask() //a为增广矩阵，要求n*n的系数矩阵可逆，运行结束后a[i][n]为第i个未知数的值
	{
		for (int i = 0, r; i < n; ++i)
		{
			for (int j = r = i; j < n; ++j)
				if (fabs(a[r][i]) < fabs(a[j][i]))
					r = j;
			if (r != i)
				swap_ranges(a[r], a[r] + n + 1, a[i]);
			for (int j = n; j >= i; --j)
				for (int k = i + 1; k < n; ++k)
					a[k][j] -= a[k][i] * a[i][j] / a[i][i];
		}
		for (int i = n - 1; ~i; --i)
		{
			for (int j = i + 1; j < n; ++j)
				a[i][n] -= a[j][n] * a[i][j];
			a[i][n] /= a[i][i];
		}
	}
};

线性基

向量线性基

add返回要插入的向量z是否与已插入的线性无关。

struct Base
{
	vector<vector<double>> v;
	Base(int N) : v(N, vector<double>(N, 0)) {} //R^N的子空间
	bool add(vector<double> x)
	{
		for (int i = 0; i < x.size(); ++i)
			if (fabs(x[i]) > EPS)
			{
				if (fabs(v[i][i]) < EPS)
					return v[i] = x, 1;
				double t = x[i] / v[i][i];
				for (int j = 0; j < x.size(); ++j)
					x[j] -= t * v[i][j];
			}
		return 0;
	}
};

异或线性基

若要查询第k小子集异或和，则把k写成二进制，对于是1的第i位，把从低位到高位第i个不为0的数异或进答案。若要判断是否有非空子集的异或和为0，如果不存在自由基，那么说明只有空集的异或值为0，需要高斯消元来判断。

struct BaseXOR
{
	vector<ll> a;
	BaseXOR() : a(64, 0) {}
	ll ask() //查询最大子集异或和
	{
		ll t = 0;
		for (int i = a.size() - 1; ~i; --i)
			t = max(t, t ^ a[i]);
		return t;
	}
	bool add(ll x)
	{
		for (int i = a.size() - 1; ~i; --i)
			if (x >> i & 1)
			{
				if (a[i])
					x ^= a[i];
				else
					return a[i] = x, 1;
			}
		return 0;
	}
	bool check(ll x) //判断一个数是否能够被异或出，0根据需要特判
	{
		for (int i = a.size() - 1; ~i; --i)
			if (x >> i & 1)
				if (x ^= a[i], !x)
					return 1;
		return 0;
	}
};