线性基

视频教程：

• G61【模板】线性基 高斯消元法 P3812 最大异或和_哔哩哔哩_bilibili
• 算法讲解136【扩展】线性基-上_哔哩哔哩_bilibili

例题：

• P3812 【模板】线性基 - 洛谷 | 计算机科学教育新生态

还需要学会高斯消元的知识。所以在本篇顺便将高斯消元的知识学了(主要来源于左程云的教学)

高斯消元

正如线性代数课堂所讲。

解决加法方程组

模板题：

• P3389 【模板】高斯消元法 - 洛谷 | 计算机科学教育新生态
• P2455 [SDOI2006] 线性方程组 - 洛谷 | 计算机科学教育新生态(可以判断无解/无穷解)

按照高斯消元的方式来解决。(只是为了防止溢出，每次挑当前列最大的)

高斯消元ADD模板

auto gauss = [&](int n)->void {//作为模板，后续不再说明
	for (int i = 1;i <= n;i++) {
		int mx = i;
		for (int j = 1;j <= n;j++) {
			if (j < i && abs(a[j][j]) >= eps)continue;
			if (abs(a[j][i]) > abs(a[mx][i])) {
				mx = j;
			}
		}
		swap(a[i], a[mx]);
		if (abs(a[i][i]) < eps)continue;
		double tmp = a[i][i];
		for (int j = i;j <= n + 1;j++) {
			a[i][j] /= tmp;
		}
		for (int j = 1;j <= n;j++) {
			if (i == j)continue;
			double rate = a[j][i] / a[i][i];
			for (int k = i;k <= n + 1;k++) {
				a[j][k] -= a[i][k] * rate;
			}
		}
	}
	};
gauss(n);

不区分无解/无穷解的

#define int long long
constexpr double eps = 1e-7;
void solve() {
    int n;cin >> n;
    vector<vector<double>> a(n + 1, vector<double>(n + 2));
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n + 1;j++) {
            int x;cin >> x;a[i][j] = x;
        }
    }

    auto gauss = [&](int n)->bool {
        for (int i = 1;i <= n;i++) {
            int mx = i;
            for (int j = i + 1;j <= n;j++) {
                if (abs(a[j][i]) > abs(a[mx][i])) {
                    mx = j;
                }
            }
            swap(a[i], a[mx]);
            if (abs(a[i][i]) < eps) return 0;
            double tmp = a[i][i];
            for (int j = i;j <= n + 1;j++) {
                a[i][j] /= tmp;
            }
            for (int j = 1;j <= n;j++) {
                if (i == j)continue;
                double rate = a[j][i] / a[i][i];
                for (int k = i;k <= n + 1;k++) {
                    a[j][k] -= a[i][k] * rate;
                }
            }
        }
        return 1;
        };

    if (!gauss(n)) {
        cout << "No Solution\n";
    } else {
        for (int i = 1;i <= n;i++) {
            cout << fixed << setprecision(2) << a[i][n + 1] << '\n';
        }
    }
}

区分无解/无穷解的

#define int long long
constexpr double eps = 1e-7;
void solve() {
    int n;cin >> n;
    vector<vector<double>> a(n + 1, vector<double>(n + 2));
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n + 1;j++) {
            int x;cin >> x;a[i][j] = x;
        }
    }

    auto gauss = [&](int n)->void {//作为模板，后续不再说明
        for (int i = 1;i <= n;i++) {
            int mx = i;
            for (int j = 1;j <= n;j++) {
                if (j < i && abs(a[j][j]) >= eps)continue;
                if (abs(a[j][i]) > abs(a[mx][i])) {
                    mx = j;
                }
            }
            swap(a[i], a[mx]);
            if (abs(a[i][i]) < eps)continue;
            double tmp = a[i][i];
            for (int j = i;j <= n + 1;j++) {
                a[i][j] /= tmp;
            }
            for (int j = 1;j <= n;j++) {
                if (i == j)continue;
                double rate = a[j][i] / a[i][i];
                for (int k = i;k <= n + 1;k++) {
                    a[j][k] -= a[i][k] * rate;
                }
            }
        }
        };
    gauss(n);
    int ans = 1;
    for (int i = 1;i <= n;i++) {
        if (abs(a[i][i]) < eps && abs(a[i][n + 1]) >= eps) {
            cout << "-1\n";return;
        }
        if (abs(a[i][i]) < eps) {
            ans = 0;
        }
    }
    if (!ans) {
        cout << ans << '\n';return;
    }
    for (int i = 1;i <= n;i++) {
        cout << "x" << i << "=" << fixed << setprecision(2) << a[i][n + 1] << '\n';
    }
}

练习：P4035 球形空间产生器
给定 $n+1$ 个点在 $n$ 维球面上，求出 $n$ 维球心。

有球的性质：球面上的点到球心的距离相等，即：$di{s}_{1,0}=di{s}_{i,0}=di{s}_{i+1,0}=di{s}_{n+1,0}$

由此可以列出 $n$ 个方程，$a_1{x}_1+a_2{x}_2+a_3{x}_3+\cdots =D$ 形式由 $di{s}_{i,0}=di{s}_{i+1,0}$ 方程得：

$a_i=2(x_{i+1}-x_i),D=\sum x_{i+1}^2-\sum x_i^2$

就得出了方程组，高斯消元即可。

#define int long long
constexpr double eps = 1e-7;
void solve() {
    int n;cin >> n;
    vector<vector<double>> a(n + 1, vector<double>(n + 2));
    vector<vector<double>> val(n + 2, vector<double>(n + 1));
    for (int i = 1;i <= n + 1;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> val[i][j];
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            a[i][j] = 2 * (val[i][j] - val[i + 1][j]);
            a[i][n + 1] += val[i][j] * val[i][j] - val[i + 1][j] * val[i + 1][j];
        }
    }
    gauss(n);

    for (int i = 1;i <= n;i++) {
        cout << fixed << setprecision(3) << a[i][n + 1] << " \n"[i == n];
    }
}

解决异或方程组

高斯消元XOR模板

        // 高斯消元解决异或方程组模版
    auto gauss = [&](int n)->void {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j < i && a[j][j] == 1) continue;
                if (a[j][i] == 1) {
                    swap(a[i], a[j]);
                    break;
                }
            }
            if (a[i][i] == 0)continue;
            for (int j = 1; j <= n; j++) {
                if (i == j || a[j][i] == 0)continue;
                for (int k = i; k <= n + 1; k++) {
                    a[j][k] ^= a[i][k];
                }
            }
        }
        };

HDU 5833:

有一个长度为 $n$ 的数组 $A$, 可能有重复值，每个数拥有的质数因子一定不超过 2000，每个数最多挑选一次

在至少要选一个数的情况下，你可以随意挑选数字乘起来乘得的结果需要是完全平方数，请问有几种挑选数字的方法，方法数可能很大，结果对 ${10}^9+7$ 取余
$1\le n\le 300$
$1\le A_i\le {10}^{18}$

Solution

对于每个完全平方数一定有：对于其某质因子的个数一定是偶数个，按照这个性质来做本题

所以先筛出 2000 以内的质数 (有 303 个)，比 $n$ 多的部分可以补 0

可以列出方程组，每个数字可以选/不选

$a_{i,j}$ 代表第 $i$ 个质数对于 $va{l}_j$ 来说是有奇数个(1)还是偶数个(0)质因子，可以列出 XOR 方程组

最终得出的结果是 $x_i$ 要还是不要(0/1)

现在得到的矩阵再经过高斯消元，得到的矩阵可能后面几行是全为 0 的，即为自由元。

这些自由元是可以影响主元的行为，即自由元确定了则主元也被确定了，所以这里的方案数是由自由元决定的，可以自行决定选/不选，自由元个数为 n - 主元个数，方案数即 $2^{\text{count(free element)}}-1$

需要排除所有都为 0 的情况(这种情况默认全不选，这种情况会导致没有数选择，而题目要求 至少选择一个数)

#define int long long
constexpr int mod = 1e9 + 7;
int t = 0;
void solve() {
    int n;cin >> n;
    vector<int> val(n + 1), power(n + 1);
    for (int i = 1;i <= n;i++)cin >> val[i];
    power[0] = 1;
    for (int i = 1;i <= n;i++)power[i] = power[i - 1] * 2 % mod;

    int m = primes.size();
    vector<vector<int>> a(m + 1, vector<int>(m + 2));

    for (int i = 1;i <= n;i++) {
        int cur = val[i], j = 1;
        for (auto p : primes) {
            while (cur % p == 0) {
                cur /= p;a[j][i] ^= 1;
            }
            j++;
        }
    }

    // 高斯消元解决异或方程组模版
    gauss(m);
    
    int ans = 0;
    for (int i = 1;i <= m;i++) {
        if (a[i][i] == 1) {
            ans++;
        }
    }
    cout << "Case #" << ++t << ":\n";
    cout << power[n - ans] - 1 << '\n';
}

P2962 Lights G

给出一张 $n$ 个点 $m$ 条边的无向图，每个点的初始状态都为 $0$。

你可以操作任意一个点，操作结束后该点以及所有与该点相邻的点的状态都会改变，由 $0$ 变成 $1$ 或由 $1$ 变成 $0$。

你需要求出最少的操作次数，使得在所有操作完成之后所有 $n$ 个点的状态都是 $1$。

Solution

题意和 Problem - G - Codeforces 有点像

本题分为两个部分：唯一解和多解的情况

初始状态每个点都只和自己相关，每次改变只改变自己，则 $a_{i,i}=1,a_{i,n+1}=1$，加入边之后，对于两个点是互相影响依赖的，则 $a_{u,v}=1,a_{v,u}=1$，这样方程组就列好了，直接高斯消元。

若有唯一解则直接输出主元需要操作的个数即可。

若有多解，从 $n\to 1$ 搜索，若遇到自由元，则都有两种选择：选/不选，当自由基确定后，则主元也确定了。

当遇到主元后，则后面的自由基这时已经有了一个分支，则主元是确定的，可以直接计算出来主元的选择(0/1)，经过搜索后就可以处理全部可能，这时的就是最小的操作个数。

void solve() {
    int n, m;cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(n + 2));
    for (int i = 1;i <= n;i++) {
        a[i][i] = 1;a[i][n + 1] = 1;
    }
    for (int i = 1;i <= m;i++) {
        int u, v;cin >> u >> v;
        a[u][v] = 1;a[v][u] = 1;
    }
    // 高斯消元解决异或方程组模版
    gauss(n);

    int ans = 0;

    vector<int> op(n + 1);

    auto dfs = [&](auto self, int i, int num)->void {
        if (num >= ans) return;//剪枝
        if (i == 0) //当搜到最后的时候，更新答案
            ans = num;
        } else {
            if (a[i][i] == 0) {
                op[i] = 0;
                self(self, i - 1, num);
                op[i] = 1;
                self(self, i - 1, num + 1);
            } else {
                int cur = a[i][n + 1];
                for (int j = i + 1;j <= n;j++) {
                    if (a[i][j] == 1)cur ^= op[j];
                }
                self(self, i - 1, num + cur);
            }
        }
        };

    int ok = 1;

    for (int i = 1;i <= n;i++) {
        if (a[i][i] == 0)ok = 0;
    }
    if (ok) {
        for (int i = 1;i <= n;i++) {
            if (a[i][n + 1] == 1) {
                ans++;
            }
        }
    } else {
        ans = n;
        dfs(dfs, n, 0);
    }
    cout << ans << '\n';
}

P2447 外星千足虫

根据题目意思感觉是很板的高斯消元，但是数据范围 $n\le 1000$，$n^3$ 会超时，但是若进行位运算压缩后就是 $\frac{n^3}{64}\approx 1.5\times {10}^7$ 就不会超时。

直接做似乎也能过 (数据太水了)，正解是 $O(\frac{n^3}{w})$

bitset 可以直接莽过去(100ms)，直接 $n^3$ 是 1500ms

所以不需要掌握左的位图技巧，bitset 即可。

bitset<2002> a[2003];
void solve() {
    int n, m;cin >> n >> m;
    int s = max(n, m);
    // vector<vector<int>> a(s + 1, vector<int>(s + 2));
    for (int i = 1;i <= m;i++) {
        string ss;cin >> ss;int x;cin >> x;
        for (int j = 1;j <= n;j++) {
            a[i][j] = ss[j - 1] - '0';
            a[i][s + 1] = x;
        }
    }
    int ans = 0;
    // 高斯消元解决异或方程组模版
    auto gauss = [&](int n)->void {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j < i && a[j][j] == 1) continue;
                if (a[j][i] == 1) {
                    swap(a[i], a[j]);
                    ans = max(ans, j);
                    break;
                }
            }
            if (a[i][i] == 0)continue;
            for (int j = 1; j <= n; j++) {
                if (i == j || a[j][i] == 0)continue;
                a[j] ^= a[i];
            }
        }
        };
    gauss(s);
    int ok = 1;
    for (int i = 1;i <= n;i++) {
        if (a[i][i] == 0) {
            ok = 0;break;
        }
    }
    if (ok) {
        cout << ans << '\n';
        for (int i = 1;i <= n;i++) {
            if (a[i][s + 1] == 1) {
                cout << "?y7M#\n";
            } else {
                cout << "Earth\n";
            }
        }
    } else {
        cout << "Cannot Determine\n";
    }
}

解决同余方程组

高斯消元同余模板

    auto gauss = [&](int n) {
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) {
                if (j < i && a[j][j] != 0)continue;
                if (a[j][i] != 0) {
                    swap(a[i], a[j]);break;
                }
            }
            if (a[i][i] == 0)continue;
            for (int j = 1;j <= n;j++) {
                if (i == j || a[j][i] == 0)continue;
                int d = __gcd(a[j][i], a[i][i]);
                int x = a[i][i] / d, y = a[j][i] / d;
                if (j < i && a[j][j] != 0) {
                    a[j][j] = (a[j][j] * x) % mod;
                }
                for (int k = i;k <= n + 1;k++) {
                    a[j][k] = ((a[j][k] * x - a[i][k] * y) % mod + mod) % mod;
                }
            }
        }
        for (int i = 1;i <= n;i++) {
            if (a[i][i] != 0) {
                int ok = 0;
                for (int j = i + 1;j <= n;j++) {
                    if (a[i][i] != 0) {
                        ok = 1;break;
                    }
                }
                if (!ok) {
                    a[i][n + 1] = a[i][n + 1] * inv(a[i][i]) % mod;
                    a[i][i] = 1;
                }
            }
        }
        };

HDU 5755

求格子全变成 0 的操作方案

有一个 $n\times m$ 的二维网格，给定每个网格的初始值，一定是 0、1、2 中的一个

有一个神奇的刷子，一旦在某个网格处刷一下，该网格会获得 2 的加成
并且该网格上、下、左、右的格子，都会获得 1 的加成

每个格子操作之后都会 $mod3$

最终目标是所有网格都变成 0，题目保证一定有解，但不保证唯一解
得到哪一种方案都可以，打印一共需要刷几下，并且把操作方案打印出来

对于每个网格，受到影响的只有自己及其周边四格的格子，方程中自己系数为 2，周边为 1，其余全为 0

可以列出方程。方程的等号右侧为 $3-x$

由于题目可以输出任意解，所以在有多解时将所有自由元全部置 0 (即主元不再受到自由元的限制) 即可得到一组合法解。

const int mod = 3;
int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
void solve() {
    int n, m;cin >> n >> m;
    vector<vector<int>> a(n * m + 1, vector<int>(n * m + 2));
    for (int i = 1;i <= n * m;i++) {
        int x;cin >> x;a[i][n * m + 1] = (3 - x) % mod;
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            int x = (i - 1) * m + j;
            a[x][x] = 2;
            for (int k = 0;k < 4;k++) {
                int cx = i + dx[k], cy = j + dy[k];
                if (cx<1 || cy<1 || cx>n || cy>m)continue;
                a[x][(cx - 1) * m + cy] = 1;
            }
        }
    }
    auto gauss = [&](int n) {
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) {
                if (j < i && a[j][j] != 0)continue;
                if (a[j][i] != 0) {
                    swap(a[i], a[j]);break;
                }
            }
            if (a[i][i] == 0)continue;
            for (int j = 1;j <= n;j++) {
                if (i == j || a[j][i] == 0)continue;
                int d = __gcd(a[j][i], a[i][i]);
                int x = a[i][i] / d, y = a[j][i] / d;
                if (j < i && a[j][j] != 0) {
                    a[j][j] = (a[j][j] * x) % mod;
                }
                for (int k = i;k <= n + 1;k++) {
                    a[j][k] = ((a[j][k] * x - a[i][k] * y) % mod + mod) % mod;
                }
            }
        }
        for (int i = 1;i <= n;i++) {
            if (a[i][i] != 0) {
                a[i][n + 1] = a[i][n + 1] * inv(a[i][i]) % mod;
            }
        }
        };

    gauss(n * m);

    int ans = 0;
    for (int i = 1;i <= n * m;i++) {
        ans += a[i][n * m + 1];
    }
    cout << ans << '\n';
    int idx = 1;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            while (a[idx][n * m + 1] > 0) {
                a[idx][n * m + 1]--;
                cout << i << " " << j << '\n';
            }
            idx++;
        }
    }
}

练习：Widget Factory - POJ 2947 - Virtual Judge ：

直接列出方程，得到 $x_i$，由于题目有 $x_i\in [3,9]$ 所以可以唯一确定 $x_i$

线性基

分为普通消元(贪心法)和高斯消元，两种方式都是 $O(n\times m)$ 的，异或空间线性基大小是 $O(m)$，$m$ 为最大数字的位数。

高斯消元中能得到非 0 异或和第 $k$ 小，当出现 0 转换一下即可。

    auto insert = [&](int x) {//模板类型
        for (int i = 63;i >= 0;i--) {
            if (x >> i & 1) {
                if (bsc[i] == 0) {
                    bsc[i] = x;return 1;
                }
                x ^= bsc[i];
            }
        }
        return 0;
        };

最大异或和

P3812 【模板】线性基 - 洛谷 | 计算机科学教育新生态
$n$ 个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

使用普通消元就可以解决

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++) cin >> a[i];
    vector<int> bsc(64);

    auto insert = [&](int x) {//模板类型
        for (int i = 63;i >= 0;i--) {
            if (x >> i & 1) {
                if (bsc[i] == 0) {
                    bsc[i] = x;return 1;
                }
                x ^= bsc[i];
            }
        }
        return 0;
        };

    for (int i = 1;i <= n;i++)insert(a[i]);

    int ans = 0;
    for (int i = 63;i >= 0;i--) {
        ans = max(ans, ans ^ bsc[i]);
    }
    cout << ans << '\n';
}

第 k 小异或和

k 大异或和

可以通过普通消元/高斯消元处理。

普通消元：

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> bsc(64);
    auto insert = [&](int x) {
        for (int i = 63;i >= 0;i--) {
            if (x >> i & 1) {
                if (bsc[i] == 0) {
                    bsc[i] = x;return 1;
                }
                x ^= bsc[i];
            }
        }
        return 0;
        };
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;insert(x);
    }

    for (int i = 63;i >= 0;i--) {//在原来的基础上再次消元
        for (int j = i - 1;j >= 0;j--) {
            if (bsc[i] >> j & 1)bsc[i] ^= bsc[j];
        }
    }
    vector<int> a;
    for (int i = 0;i <= 63;i++) {
        if (bsc[i])a.push_back(bsc[i]);
    }

    int zero = a.size() != n;

    int m;cin >> m;
    while (m--) {
        int k;cin >> k;
        if (zero)k--;
        if (k == 0) {
            cout << "0\n";continue;
        }
        if (k >= (1ll << a.size())) {
            cout << "-1\n";continue;
        }
        int ans = 0;
        for (int i = 0;i <= __lg(k);i++) {
            if (k >> i & 1) {
                ans ^= a[i];
            }
        }
        cout << ans << '\n';
    }
}

左：

#define int long long
int a[100010];
void solve() {
    int n;cin >> n;
    for (int i = 1;i <= n;i++)cin >> a[i];

    int len = 1;
    for (int i = 50;i >= 0;i--) {
        for (int j = len;j <= n;j++) {
            if (a[j] >> i & 1) {
                swap(a[j], a[len]);break;
            }
        }
        if ((a[len] >> i & 1) ^ 1)continue;//这一步若开vector(n+1) 则会出错
        for (int j = 1;j <= n;j++) {
            if (j == len || (a[j] >> i & 1 ^ 1))continue;
            a[j] ^= a[len];
        }
        len++;
    }
    len--;

    int zero = len != n;

    int m;cin >> m;
    while (m--) {
        int k;cin >> k;
        if (zero && k == 1) {
            cout << "0\n";continue;
        }
        if (zero)k--;

        if (k >= (1ll << len)) {
            cout << "-1\n";continue;
        }
        int ans = 0;
        for (int i = 0;i <= __lg(k);i++) {
            if (k >> i & 1) {
                ans ^= a[len - i];
            }
        }
        cout << ans << '\n';
    }
}

P4570 元素

有 $n$ 个矿石，每个矿石有编号和其魔力值。当选择的矿石的元素序号非空子集的异或和为 0 时将会魔法抵消(全部消失)，求选择后能得到的最大魔力值.

按照魔力值排序，进行线性基即可

void solve() {
    int n;cin >> n;
    vector<array<int, 2>> a(n + 1);
    vector<int> bsc(64);
    for (int i = 1;i <= n;i++)cin >> a[i][0] >> a[i][1];
    
    int ans = 0;
    sort(a.begin() + 1, a.end(), [](auto x, auto y) {
        return x[1] > y[1];
        });
    for (int i = 1;i <= n;i++) {
        if (insert(a[i][0])) {
            ans += a[i][1];
        }
    }
    cout << ans << '\n';
}

ETC...

我认为现在在这上面的时间有点多了，先到这吧，至于线性基 (下) 就之后再说了。