高斯消元 线性空间 线性基 [数学]

高斯消元 模板

https://www.luogu.org/problem/P3389

#include <bits/stdc++.h>
#define debug(x, str) cout << (str) << " = [ << : " << (x) << " ]" << endl;
#define fastio ios::sync_with_stdio(0),cin.tie(0);
#define fir first
#define sec second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;

double A[120][120];
int n;

void Gauss() {

}

int main() {
	cin >> n;
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < n + 1; j ++) cin >> A[i][j];

	Gauss();
	int f1 = 0, f2 = 0;
	for(int i = 0, r; i < n; i ++) {
		r = i;
		for(int j = i + 1; j < n; j ++)
			if(fabs(A[j][i]) > fabs(A[r][i])) r = j;
		if(r != i) for(int j = 0; j < n + 1; j ++) swap(A[r][j], A[i][j]);
		if(A[i][i] == 0) continue;
		double p = A[i][i];
		for(int j = 0; j < n + 1; j ++)
			A[i][j] /= p;
		for(int j = 0; j < n; j ++)
			if(i != j) {
				double o = A[j][i];
				for(int k = 0; k < n + 1; k ++)
					A[j][k] -= A[i][k]*o;
			}
	}

	for(int i = 0; i < n; i ++) {
		int res = 0;
		for(int j = 0; j < n + 1; j ++)
			if(!A[i][j]) res++;
		if(res == n && A[i][n])
			f1 = 1;
		if(res == n + 1)
			f2 = 1;

	}
// No Solution // f1 无解 f2 无穷的解 
	if(f1 || f2) cout << "No Solution" << endl;
	else if(f2) cout << 0 << endl;
	else {
		for(int i = n - 1; i >= 0; i --) {
			for(int j = i + 1; j < n; j ++)
				A[i][n] -= A[j][n] * A[i][j];
			A[i][n] /= A[i][i];
		}
		for(int i = 0; i < n; i ++) {
			printf("%.2lf\n", A[i][n]);
		}
	}
	return 0;
}

https://www.luogu.org/problem/P2455

#include <bits/stdc++.h>
#define debug(x, str) cout << (str) << " = [ << : " << (x) << " ]" << endl;
#define fastio ios::sync_with_stdio(0),cin.tie(0);
#define fir first
#define sec second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;

double A[120][120];
int n;

void Gauss() {

}

int main() {
	cin >> n;
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < n + 1; j ++) cin >> A[i][j];

	Gauss();
	int f1 = 0, f2 = 0;
	for(int i = 0, r; i < n; i ++) {
		r = i;
		for(int j = i + 1; j < n; j ++)
			if(fabs(A[j][i]) > fabs(A[r][i])) r = j;
		if(r != i) for(int j = 0; j < n + 1; j ++) swap(A[r][j], A[i][j]);
		if(A[i][i] == 0) continue;
		double p = A[i][i];
		for(int j = 0; j < n + 1; j ++)
			A[i][j] /= p;
		for(int j = 0; j < n; j ++)
			if(i != j) {
				double o = A[j][i];
				for(int k = 0; k < n + 1; k ++)
					A[j][k] -= A[i][k]*o;
			}
	}

	for(int i = 0; i < n; i ++) {
		int res = 0;
		for(int j = 0; j < n + 1; j ++)
			if(!A[i][j]) res++;
		if(res == n && A[i][n])
			f1 = 1;
		if(res == n + 1)
			f2 = 1;

	}

	if(f1) cout << -1 << endl;
	else if(f2) cout << 0 << endl;
	else {
		for(int i = n - 1; i >= 0; i --) {
			for(int j = i + 1; j < n; j ++)
				A[i][n] -= A[j][n] * A[i][j];
			A[i][n] /= A[i][i];
		}
		for(int i = 0; i < n; i ++) {
			if(A[i][n] != 0) printf("x%d=%.2lf\n", i + 1, A[i][n]);
			else cout << "x" << i + 1 << "=" << 0 << endl;
		}
	}
	return 0;
}

线性基模板

https://www.luogu.org/problem/P3812
问有多少个数字能通过A的子集进行异或运算得出并且也能通过B的子集异或运算得出。子集可以是空集
求A的线性基和B的线性基交集的秩，假设为x，那么答案就是 2的x次方。
线性基交集的秩=A的线性基的秩+B的线性基的秩-A和B线性基的并的秩

#include <bits/stdc++.h>
#define debug(x, str) cout << (str) << " = [ << : " << (x) << " ]" << endl;
#define fastio ios::sync_with_stdio(0),cin.tie(0);
#define fir first
#define sec second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 1e5 + 5;

struct Linebasis {
	ll p[65], b[65];
	int cnt;
	bool flag;

	void init() {
		memset(p, 0, sizeof(p));
		memset(b, 0, sizeof(b));
		cnt = 0;
		flag = false;
	}

	bool insert(ll x) {
		for(int i = 62; i >= 0; i--)
			if((x >> i) & 1) {
				if(!p[i]) {
					p[i] = x;
					break;
				}
				x ^= p[i];
			}
		if(x) cnt++;
		else flag = true; // 有0;
		return x > 0;
	}

	Linebasis operator +(const Linebasis & r) const {
		Linebasis res = r;
		for(int i = 0; i <= 62; i++) {
			if(p[i])
				res.insert(p[i]);
		}
		return res;
	}

	ll querymax(ll x = 0) {
		ll res = x;
		for(int i = 62; i >= 0; i--) {
			if((res ^ p[i]) > res) res ^= p[i];
		}
		return res;
	}

	ll querymin() {
		for(int i = 0; i <= 62; i++)
			if(p[i]) return p[i];
		return 0;
	}

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

	ll kthmin(ll k) {
		if(flag) k--; // 减 0 
		ll res = 0;
		if(!k) return 0;
		if(k >= (1ll << cnt)) return -1;
		for(int i = cnt; i >= 0; i--) {
			if((k >> i) & 1) res ^= b[i];
		}
		return res;
	}
} sol;

int main() {
	int n, T, q;
	ll k;
	scanf("%d", &T);
	for(int kase = 1; kase <= T; kase++) {
		sol.init();
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			ll x;
			scanf("%lld", &x);
			sol.insert(x);
		}
		scanf("%d", &q);
		printf("Case #%d:\n", kase);
		sol.rebuild();
		while(q--) {
			scanf("%lld", &k);
			printf("%lld\n", sol.kthmin(k));
		}
	}
	return 0;
}