高斯消元，线性基，TODO

线性代数

高斯消元

模板（可以求唯一解，判无解和无穷多组解）：

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
const double eps = 1e-5;

double a[N][N];
int n;

void calc(int x, int y, double c) {
    for (int i = 1; i <= n + 1; i++) {
        a[y][i] += (a[x][i] * c);
    }
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 1; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        // 如果第i行第i列是0，则找下面其他行的第i列非0的行，交换一下
        if (fabs(a[i][i]) < eps) {
            for (int j = i + 1; j <= n; j++) {
                if (fabs(a[j][i]) > eps) {
                    swap(a[j], a[i]);
                    break;
                }
            }
        }

        // 如果第i列都是0，就不管了，最后再说
        if (fabs(a[i][i]) < eps) {
            continue;
        }

        // 把除了本行之外的其他行的第i列都消成0
        for (int j = 1; j < i; j++) {
            if (fabs(a[j][i]) > eps) {
                calc(i, j, -a[j][i] / a[i][i]);
            }
        }

        for (int j = i + 1; j <= n; j++) {
            if (fabs(a[j][i]) > eps) {
                calc(i, j, -a[j][i] / a[i][i]);
            }
        }
    }

    bool flag = true;
    for (int i = 1; i <= n; i++) {
        if (fabs(a[i][i]) < eps) {
            flag = false;
        }
    }

    if (flag) {
        for (int i = 1; i <= n; i++) {
            printf("%.2lf\n", a[i][n + 1] / a[i][i]);
        }
    } else {
        bool s = true;
        for (int i = 1; i <= n; i++) {
            if (fabs(a[i][i]) < eps) {
                if (fabs(a[i][n + 1]) > eps) {
                    puts("No solution");
                    s = false;
                    break;
                }
            }
        }
        if (s) {
            puts("Infinite group solutions");
        }
    }

    return 0;
}

具体应用就是解方程组，求行列式，求矩阵的逆等。对于解方程组，需要对问题进行转化获得解方程组的需求，构造出正确的需要求解的方程组。

矩阵乘法

本题要求的是某个给定的串在多少个长度为 $n$ 的串中没出现过，是一个带有相对禁止位置的排列问题。