矩阵

typedef array<array<ll, N>, N> Mat;

乘法和快速幂

Mat operator*(const Mat &a, const Mat &b)
{
	Mat r;
	for (int i = 0; i < r.size(); ++i)
		for (int j = 0; j < r.size(); ++j)
			for (int k = r[i][j] = 0; k < r.size(); ++k)
				M.qadd(r[i][j], M.mul(a[i][k], b[k][j]));
	return r;
}
Mat pow(Mat a, ll b)
{
	Mat r;
	for (int i = 0; i < r.size(); ++i)
		for (int j = 0; j < r[i].size(); ++j)
			r[i][j] = i == j;
	for (; b; b >>= 1, a = a * a)
		if (b & 1)
			r = r * a;
	return r;
}

行列式

ll det(Mat a, int n)
{
	ll ans = 1;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i + 1; j < 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;
}

高斯消元

void GaussElimination(Mat &a, int n) //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].begin(), a[r].begin() + 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;
	}
};