高斯消元法

3
1 1 1 9
2 -1 3 13
3 2 -1 8

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 105;
const double EPS = 1e-8;
int n;
double a[MAXN][MAXN];
double x[MAXN];

int main() {
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n + 1; j++)
            scanf("%lf", &a[i][j]);

    int row = 1;                       // 当前正在确定主元的行
    for (int col = 1; col <= n; col++) {
        // 选主元：在 row..n 中挑 |a[i][col]| 最大的
        int piv = row;
        for (int i = row; i <= n; i++)
            if (fabs(a[i][col]) > fabs(a[piv][col])) piv = i;
        if (fabs(a[piv][col]) < EPS) continue;   // 该列无主元 → 自由变量

        for (int j = col; j <= n + 1; j++) swap(a[row][j], a[piv][j]);

        for (int i = 1; i <= n; i++) {          // Gauss–Jordan：上下一起消
            if (i == row) continue;
            double f = a[i][col] / a[row][col];
            if (fabs(f) < EPS) continue;
            for (int j = col; j <= n + 1; j++)
                a[i][j] -= f * a[row][j];
        }
        row++;
    }

    // 检查矛盾行：系数全 0 但常数非 0 → 无解
    for (int i = row; i <= n; i++)
        if (fabs(a[i][n + 1]) > EPS) { printf("No Solution\n"); return 0; }

    if (row - 1 < n) { printf("Multiple Solutions\n"); return 0; }

    // 每行只剩主元列非零 → 常数/主元 = 解
    for (int i = 1; i <= n; i++) {
        int c = -1;
        for (int j = 1; j <= n; j++) if (fabs(a[i][j]) > EPS) { c = j; break; }
        x[c] = a[i][n + 1] / a[i][c];
    }
    for (int i = 1; i <= n; i++) printf("%.2f\n", x[i]);
    return 0;
}

#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;

const int MAXN = 2005;
int n;
bitset<MAXN> a[MAXN];              // 第 0..n-1 位是系数，第 n 位是常数

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= n; j++) {
            int v; scanf("%d", &v);
            if (v) a[i].set(j);
        }

    int rank_ = 0, row = 0;
    for (int col = 0; col < n && row < n; col++) {
        // 找一个该列为 1 的行当主元行（不需要选最大值）
        int piv = -1;
        for (int i = row; i < n; i++)
            if (a[i].test(col)) { piv = i; break; }
        if (piv == -1) continue;              // 整列都是 0 → 该未知数自由

        swap(a[row], a[piv]);
        for (int i = 0; i < n; i++)          // 上下所有该列为 1 的行整行异或
            if (i != row && a[i].test(col)) a[i] ^= a[row];
        row++; rank_++;
    }

    // 找矛盾行：系数全 0，常数位为 1 → 0 = 1，无解
    for (int i = row; i < n; i++) {
        bool coeffZero = true;
        for (int j = 0; j < n; j++) if (a[i].test(j)) { coeffZero = false; break; }
        if (coeffZero && a[i].test(n)) { printf("0\n"); return 0; }
    }

    // 解的个数 = 2^(n - rank)，用快速幂或移位输出
    printf("2^%d\n", n - rank_);      // 实际题目常要求输出对 1e9+7 取模的结果
    return 0;
}

const long long P = 1000000007;
long long a[105][106];

long long qpow(long long b, long long e) {
    long long r = 1; b %= P;
    while (e) { if (e & 1) r = r * b % P; b = b * b % P; e >>= 1; }
    return r;
}
long long inv(long long v) { return qpow(v, P - 2); }   // 费马小定理

void gauss_mod() {
    for (int col = 1; col <= n; col++) {
        int piv = -1;
        for (int i = col; i <= n; i++) if (a[i][col]) { piv = i; break; }
        if (piv == -1) continue;                    // 无主元 → 自由变量
        if (piv != col) for (int j = col; j <= n + 1; j++) swap(a[piv][j], a[col][j]);

        long long iv = inv(a[col][col]);                // 归一化：主元变成 1
        for (int j = col; j <= n + 1; j++) a[col][j] = a[col][j] * iv % P;

        for (int i = 1; i <= n; i++) {
            if (i == col || !a[i][col]) continue;
            long long f = a[i][col];
            for (int j = col; j <= n + 1; j++)
                a[i][j] = ((a[i][j] - f * a[col][j]) % P + P) % P;
        }
    }
}

long long det = 1;
for (int col = 1; col <= n; col++) {
    int piv = -1;
    for (int i = col; i <= n; i++) if (a[i][col]) { piv = i; break; }
    if (piv == -1) { det = 0; break; }        // 整列全 0 → 行列式为 0
    if (piv != col) {                             // 交换两行 → 变号
        for (int j = 1; j <= n; j++) swap(a[piv][j], a[col][j]);
        det = (P - det) % P;
    }
    det = det * a[col][col] % P;                   // 累乘对角元
    long long iv = inv(a[col][col]);
    for (int i = col + 1; i <= n; i++) {          // 只消下方，用倍加（不改变行列式）
        if (!a[i][col]) continue;
        long long f = a[i][col] * iv % P;
        for (int j = col; j <= n; j++)
            a[i][j] = ((a[i][j] - f * a[col][j]) % P + P) % P;
    }
}
printf("%lld\n", det);