线性代数模板
高斯消元法
/*
* 高斯-约旦消元法
* 可以修改为解异或方程组 修改策略为
* a+b -> a^b
* a-b -> a^b
* a*b -> a&b
* a/b -> a*(b==1)
* */
void gauss(int n) {
vector<bool> vis(n, false);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (vis[j]) continue;
if (fabs(a[j][i]) > eps) {
vis[i] = true;
for (int k = 0; k <= n; ++k) swap(a[i][k], a[j][k]);
break;
}
}
if (fabs(a[i][i]) < eps) continue;
for (int j = 0; j <= n; ++j) {
if (i != j && fabs(a[j][i]) > eps) {
double res = a[j][i] / a[i][i];
for (int k = 0; k <= n; ++k) a[j][k] -= a[i][k] * res;
}
}
}
}
int check(int n) { // 解系检测
int status = 1;
for (int i = n - 1; i >= 0; --i) {
if (fabs(a[i][i]) < eps && fabs(a[i][n]) > eps) return -1; // 无解
if (fabs(a[i][i]) < eps && fabs(a[i][n]) < eps) status = 0; // 无穷解
ans[i] = a[i][n] / a[i][i];
if (fabs(ans[i]) < eps) ans[i] = 0;
}
return status; // 唯一解或无穷解
}
bitset版高斯消元法
const int SIZE = 1001;
bitset<SIZE> a[SIZE];
int ans[SIZE];
void gauss(int n) { // bitset版高斯消元 用于求解异或线性方程组
bitset<SIZE> vis;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (vis[j]) continue;
if (a[j][i]) {
vis.set(i);
swap(a[i], a[j]);
break;
}
}
if (!a[i][i]) continue;
for (int j = 0; j <= n; ++j) {
if (i != j && (a[j][i] & a[i][i])) {
a[j] ^= a[i];
}
}
}
}
矩阵树定理/任意模数行列式求值
/*
* 矩阵树定理
* 有向图：若 u->v 有一条权值为 w 的边 基尔霍夫矩阵 a[v][v] += w, a[v][u] -= w
* 生成树数量为除去 根所在行和列 后的n-1阶行列式的值
* 无向图：若 u->v 有一条权值为 w 的边 基尔霍夫矩阵 a[v][v] += w, a[v][u] -= w, a[u][u] += w, a[u][v] -= w
* 生成树数量为除去 任意一行和列 后的n-1阶行列式的值
* 无权图则边权默认为1
* */
typedef long long ll;
typedef unsigned long long u64;
int a[SIZE][SIZE];
int gauss(int a[][SIZE], int n) { // 任意模数求行列式 O(n^2(n + log(mod)))
int ans = 1;
for (int i = 1; i <= n; i++) {
int* x = 0, * y = 0;
for (int j = i; j <= n; j++) {
if (a[j][i] && (x == NULL || a[j][i] < x[i])) {
x = a[j];
}
}
if (x == 0) {
return 0;
}
for (int j = i; j <= n; j++) {
if (a[j] != x && a[j][i]) {
y = a[j];
for (;;) {
int v = md - y[i] / x[i], k = i;
for (; k + 3 <= n; k += 4) {
y[k + 0] = (y[k + 0] + u64(x[k + 0]) * v) % md;
y[k + 1] = (y[k + 1] + u64(x[k + 1]) * v) % md;
y[k + 2] = (y[k + 2] + u64(x[k + 2]) * v) % md;
y[k + 3] = (y[k + 3] + u64(x[k + 3]) * v) % md;
}
for (; k <= n; ++k) {
y[k] = (y[k] + u64(x[k]) * v) % md;
}
if (!y[i]) break;
swap(x, y);
}
}
}
if (x != a[i]) {
for (int k = i; k <= n; k++) {
swap(x[k], a[i][k]);
}
ans = md - ans;
}
ans = 1LL * ans * a[i][i] % md;
}
return ans;
}
线性基
struct linearBasis {
/* 线性基性质：
* 1.若a[i]!=0（即主元i存在）
* 则线性基中只有a[i]的第i位是1（只存在一个主元）
* 且此时a[i]的最高位就是第i位
* 2.将数组a插入线性基 假设有|B|个元素成功插入
* 则数组a中每个不同的子集异或和都出现 2^(n-|B|) 次
* */
static const int MAXL = 60;
long long a[MAXL + 1];
int id[MAXL + 1];
int zero;
/* 0的标志位 =1则表示0可以被线性基表示出来
* 求第k大元素时 需要注意题意中线性基为空时是否可以表示0
* 默认不可以表示 有必要时进行修改即可
* */
linearBasis() {
zero = 0;
fill(a, a + MAXL + 1, 0);
}
long long& operator [] (int k) { return a[k]; }
bool insert(long long x) {
for (int j = MAXL; ~j; j--) {
if (!(x & (1LL << j))) { // 如果 x 的第 j 位为 0，则跳过
continue;
}
if (a[j]) { // 如果 a[j] != 0，则用 a[j] 消去 x 的第 j 位上的 1
x ^= a[j];
} else { // 找到插入位置
for (int k = 0; k < j; k++) {
if (x & (1LL << k)) { // 如果x存在某个低位线性基的主元k则消去
x ^= a[k];
}
}
for (int k = j + 1; k <= MAXL; k++) {
if (a[k] & (1LL << j)) { // 如果某个高位线性基存在主元j则消去
a[k] ^= x;
}
}
a[j] = x;
return true;
}
}
zero = 1;
return false;
}
long long query_max() { // 最大值
long long res = 0;
for (int i = MAXL; ~i; i--) {
res ^= a[i];
}
return res;
}
long long query_max(long long x) { // 线性基异或x的最大值
for (int i = MAXL; ~i; i--) {
if ((x ^ a[i]) > x) {
x ^= a[i];
}
}
return x;
}
long long query_min() { // 最小值
for (int i = 0; i < MAXL; i++) {
if (a[i]) {
return a[i];
}
}
return -1; // 线性基为空
}
long long query_min(long long x) { // 线性基异或x的最小值
for (int i = MAXL; ~i; i--) {
if ((x ^ a[i]) < x) {
x ^= a[i];
}
}
return x;
}
int count(long long x) { // 元素 x 能否被线性基内元素表示
int res = 0;
vector<long long> b(MAXL + 1);
for (int i = 0; i <= MAXL; i++) {
b[i] = a[i];
}
res = this->insert(x);
for (int i = 0; i <= MAXL; i++) {
a[i] = b[i];
}
return !res; // 成功插入则无法表示 失败则可以表示
}
int size() { // 线性基有效元素数量
int res = 0;
for (int i = 0; i <= MAXL; i++) {
if (a[i]) {
res++;
}
}
return res;
}
long long kth_element(long long k) { // 第k大元素
vector<long long> b;
for (int i = 0; i <= MAXL; i++) {
if (a[i]) {
b.push_back(a[i]);
}
}
if (zero) {
if (--k == 0) {
return 0;
}
}
if (k >= (1LL << this->size())) { // k超过了线性基可以表示的最大数量
return -1;
}
long long res = 0;
for (int i = 0; i <= MAXL; i++) {
if (k & (1LL << i)) {
res ^= b[i];
}
}
return res;
}
long long rank(long long x) { // 元素x在线性基内的排名（默认不考虑0）
vector<long long> b;
for (int i = 0; i <= MAXL; i++) {
if (a[i]) {
b.push_back(1LL << i);
}
}
long long res = 0;
for (int i = 0; i < (int)b.size(); i++) {
if (x & b[i]) {
res |= (1LL << i);
}
}
return res;
}
void clear() {
zero = 0;
fill(a, a + MAXL + 1, 0);
}
};
线性基naive
struct simpleLinearBasis {
int n;
vector<long long> a;
simpleLinearBasis(int n_ = 0) { n = n_, a.resize(n, 0); }
long long& operator[] (int k) { return a[k]; }
bool insert(int x) {
for (int i = n - 1; ~i; i--) {
if ((x >> i) & 1) {
if (!a[i]) {
a[i] = x;
return true;
}
x ^= a[i];
}
}
return false;
}
};
bitset版线性基
static const int N = 501;
struct linearBasis {
static const int MAXL = 500;
bitset<N> bs[N];
linearBasis() {
for (int i = 0; i <= MAXL; i++) {
bs[i].reset();
}
}
bool insert(bitset<N> x) { // 插入向量x
for (int j = MAXL; ~j; j--) {
if (!x[j]) { // 如果 x 的第 j 位为 0，则跳过
continue;
}
if (bs[j][j]) { // 如果 a[j] != 0，则用 a[j] 消去 x 的第 j 位上的 1
x ^= bs[j];
} else { // 找到插入位置
for (int k = 0; k < j; k++) {
if (x[k]) { // 如果x存在某个低位线性基的主元k则消去
x ^= bs[k];
}
}
for (int k = j + 1; k <= MAXL; k++) {
if (bs[k][j]) { // 如果某个高位线性基存在主元j则消去
bs[k] ^= x;
}
}
bs[j] = x;
return true;
}
}
return false;
}
};
线性基x高斯消元
// a数组存线性基，b数组存给定的向量
db a[MAXL][MAXL], b[MAXL][MAXL];
bool insert(int k) { // 询问一个向量 a[0,1,2,...,k-1] 能否被已有元素线性组合出来
for (int i = 0; i < n; i++) {
if (fabs(b[k][i]) < eps) continue;
if (fabs(a[i][i]) > eps) {
db div = b[k][i] / a[i][i];
for (int j = 0; j < m; j++) {
b[k][j] -= div * a[i][j];
}
} else {
for (int j = 0; j < m; j++) {
a[i][j] = b[k][j];
}
return true;
}
}
return false;
}