【数学】矩阵的逆

struct InverseMatrix {

    static const int MOD = 1e9 + 7;
    static const int MAXN = 400 + 10;

    int n;
    ll A[MAXN][2 * MAXN];

    void Init(int n) {
        this->n = n;
        ms(A);
    }

    void ShowRight() {
        for(int i = 1; i <= n; ++i) {
            for (int j = n + 1; j <= 2 * n; ++j)
                printf("%d ", A[i][j]);
            printf("\n");
        }
    }

    ll qpow(ll x, ll n) {
        ll res = 1;
        while(n) {
            if(n & 1)
                res = res * x % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }

    int Inverse() {
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                A[i][j + n] = (j == i);
            }
        }
        for(int cur = 1; cur <= n; ++cur) {
            int pivot = cur;
            for(int i = pivot; i <= n; ++i) {
                if(A[i][cur]) {
                    pivot = i;
                    break;
                }
            }
            if(A[pivot][cur] == 0)
                // 无解
                return -1;
            if(pivot != cur) {
                for(int j = 2 * n; j >= cur; --j)
                    swap(A[pivot][j], A[cur][j]);
            }
            ll inv = qpow(A[cur][cur], MOD - 2);
            for (int j = 2 * n; j >= cur; --j)
                A[cur][j] = 1LL * A[cur][j] * inv % MOD;
            for(int i = 1; i <= n; ++i) {
                if(i == cur || A[i][cur] == 0)
                    continue;
                for (int j = 2 * n; j >= cur; --j) {
                    A[i][j] -= 1LL * A[i][cur] * A[cur][j] % MOD;
                    if(A[i][j] < 0)
                        A[i][j] += MOD;
                }
            }
        }
        // 成功
        return n;
    }

} ma;

类似的方法可以找出使得A矩阵变换到B矩阵要左乘的矩阵。

【数学】矩阵的逆

原文：https://www.cnblogs.com/purinliang/p/14333027.html