Contents
矩阵类
构造函数
struct Matrix {
int n, m;
vector< vector<int> > a;
void clear() {
vector<int> tmp(m + 1);
a.resize(0);
for (int i = 0; i <= n; i++) {
a.push_back(tmp);
}
}
Matrix(int _n, int _m) : n(_n), m(_m) {
clear();
}
Matrix(int _n) : n(_n), m(_n) {
clear();
}
Matrix() {}
};
矩阵乘法与快速幂
Matrix operator * (const Matrix &b) {
assert(m == b.n);
Matrix ans(n, b.m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= b.m; j++) {
long long tmp = 0;
for(int k = 1; k <= m; k++) {
tmp += 1LL * a[i][k] * b.a[k][j] % P;
}
ans.a[i][j] = tmp % P;
}
}
return ans;
}
Matrix operator ^ (const int &x) const {
assert(n == m);
Matrix ret(n), a = *this;
for (int i = 1; i <= n; i++) ret.a[i][i] = 1;
int b = x;
for (; b; b >>= 1, a = a * a) {
if (b & 1) {
ret = ret * a;
}
}
return ret;
}
矩阵高斯消元
得到对角矩阵。其中最后得到的 i 为矩阵的秩。如果需要得到上三角矩阵，只需将 k 从 i+1 开始遍历。
void Gauss() {
int i = 1, j = 1, r;
while (i <= n && j <= m) {
r = i;
for (int k = i; k <= n; k++) {
if (a[k][j]) {
r = k; break;
}
}
if (a[r][j]) {
if (r != i) swap(a[i], a[r]);
for (int k = j, t = ni(a[i][j]); k <= m; k++) {
a[i][k] = 1LL * a[i][k] * t % P;
}
// for (int k = i + 1; k <= n; k++)
for (int k = 1; k <= n; k++) {
if (k != i && a[k][j]) {
for (int l = j, t = a[k][j]; l <= m; l++) {
(a[k][l] += P - 1LL * t * a[i][l] % P) %= P;
}
}
}
i++;
}
j++;
}
}
矩阵求逆
注意需要首先确认矩阵满秩。
Matrix inv(Matrix A) {
int n = A.n, m = A.m;
assert(n == m);
A.m = A.n + A.n;
for (int i = 1; i <= n; i++) {
A.a[i].resize(2 * n + 1);
A.a[i][n + i] = 1;
}
A.Gauss();
Matrix ret;
ret.n = ret.m = n; ret.clear();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ret.a[i][j] = A.a[i][j + n];
}
}
return ret;
}
例题：2020牛客多校第一场 D. Quadratic Form
解线性方程组
#include <bits/stdc++.h>
using namespace std;
struct Matrix {
constexpr static double eps = 1e-13;
int n, m;
vector< vector<double> > a;
void clear() {
vector<double> tmp(m + 1);
a.resize(0);
for (int i = 0; i <= n; i++) {
a.push_back(tmp);
}
}
Matrix(int _n, int _m) : n(_n), m(_m) {
clear();
}
Matrix(int _n) : n(_n), m(_n) {
clear();
}
Matrix() {}
void rswap(int x, int y) {
swap(a[x], a[y]);
}
bool Agreater(int k, int x, int y) {
if (fabs(fabs(a[x][k]) - fabs(a[y][k])) > eps) {
return fabs(a[x][k]) > fabs(a[y][k]);
}
for (int i = k + 1; i <= n; i++) {
if (fabs(fabs(a[x][i]) - fabs(a[y][i])) > eps) {
return fabs(a[x][i]) < fabs(a[y][i]);
}
}
return false;
}
void Gauss() {
for (int i = 1; i <= n; i++) {
int r = i;
for (int j = i + 1; j <= n; j++) {
if (Agreater(i, j, r)) r = j;
}
if (r != i) rswap(r, i);
double k = a[i][i];
if (fabs(k) < eps) continue;
for (int j = i; j <= m; j++) a[i][j] /= k;
for (int j = i + 1; j <= n; j++) {
double k = a[j][i];
for (int l = i; l <= m; l++) a[j][l] -= a[i][l] * k;
}
}
for (int i = n; i; i--) {
if (a[i][i] == 0) continue;
for (int j = i - 1; j; j--) {
for (int l = n + 1; l <= m; l++) {
a[j][l] -= a[j][i] * a[i][l];
}
a[j][i] = 0;
}
}
}
int Linear_Equations() {
Gauss();
int flag = 1;
for (int i = 1; i <= n; i++){
if (fabs(a[i][i]) < eps && fabs(a[i][n+1]) > eps) {
flag = -1; break; // no answer
}
if (fabs(a[i][i]) < eps && fabs(a[i][n+1]) < eps) {
flag = 0; // multi answer
}
}
return flag;
}
};
int main(int argc, const char * argv[]) {
int n; scanf("%d", &n);
Matrix m(n, n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n + 1; j++) {
scanf("%lf", &m.a[i][j]);
}
}
int ans = m.Linear_Equations();
if (ans != 1) printf("%d\n", ans);
else {
for (int i = 1; i <= n; i++) {
printf("x%d=%.2f\n", i, m.a[i][n + 1]);
}
}
return 0;
}
异或方程组
题目大意：
给 m 个含有 n 个变量的异或方程组，保证没有矛盾，求至少需要前几个方程才能确定全部变量的解，或者无法确定确定解。
解题思路：
对异或方程组进行高斯消元，使用 bitset 优化常数。在对某一位消元时，如果需要交换两行，向下遍历到第一个该位不为 0 的行，用它更新答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 2e3 + 10;
bitset<N> a[M];
int Gauss(int n, int m) {
int i = 1, j = 1, r;
int ans = 0;
while (i <= m && j <= n) {
r = i;
for (int k = i; k <= m; k++) {
if (a[k][j]) {
r = k; ans = max(ans, k); break;
}
}
if (a[r][j]) {
if (r != i) swap(a[i], a[r]);
for (int k = 1; k <= m; k++) {
if (k != i && a[k][j]) a[k] ^= a[i];
}
i++;
}
else {
return false;
}
j++;
}
return ans;
}
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
string s, c; cin >> s >> c;
for (int j = 1; j <= n; j++) {
a[i][j] = s[j - 1] - '0';
}
a[i][n + 1] = c[0] - '0';
}
int ans = Gauss(n, m);
if (!ans) {
printf("Cannot Determine\n");
return 0;
}
printf("%d\n", ans);
for (int i = 1; i <= n; i++) {
printf(a[i][n + 1] ? "?y7M#\n" : "Earth\n");
}
return 0;
}
例题2：UVA11542 Square