题解：P4783 【模板】矩阵求逆

luckyyunji · 2025-07-25 10:29:16 · 题解

矩阵求逆

传送门

假设矩阵 A 的逆矩阵就是 B，则满足 AB=I，I 表示单位矩阵，当然 B=A^{-1}。

为了求出 A^{-1}，先思考 A 是如何变成 I，可以通过 高斯消元法 将矩阵变为单位矩阵。

然后可以发现将 A 变成 I，就相当于让 A 乘上 A^{-1}，那么对 I 进行上面这个过程，就相当于让 I 乘上 A^{-1}。即：

在代码中可以简单将 A 的右边加上（不是矩阵加法，是扩容）一个单位矩阵 I。然后让整个矩阵的左边经过初等变换变成单位矩阵，那么右边自然是逆矩阵（代码更清晰）。

总结一下就是将 A 的右边加上一个单位矩阵 I，然后高斯（高斯约旦）消元就好了。

注意，除法要用逆元。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 512;
const int MOD=1e9+7;
int a[MAXN][2*MAXN];
int n;
void print()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 2*n; j++)
        {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int x1,y1,d=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-((a/b)*y1);
    return d;
}

int solve()
{
    int curr = 0;
    for (int cur = 0; cur < n; cur++)
    {
        int maxx = curr;
        // choose max
        for (int i = curr; i < n; i++)
        {
            if (abs(a[i][cur]) > abs(a[maxx][cur]))
            {
                maxx = i;
            }
        }
        swap(a[curr], a[maxx]);
        if (!a[curr][cur])
        {
            continue;
        }
        // set x to 1
        for (int i = 2*n-1,x,y; i >= cur; i--)
        {
            //a[curr][i] /= a[curr][cur];
            if(a[curr][cur]==1) break;
            exgcd(a[curr][cur],MOD,x,y);
            a[curr][i]*=(x%MOD+MOD)%MOD;
            a[curr][i]%=MOD;
        }
        for (int i = 0; i < n; i++)
        {
            if (i == curr)
            {
                continue;
            }
            // set others to 0
            for (int j = cur; j < 2*n; j++)
            {
                if (j == cur)
                {
                    continue;
                }
                a[i][j] = (a[i][j] - a[i][cur] * a[curr][j] % MOD + MOD) % MOD;
                //a[i][j] = (a[i][j] - a[i][cur] * a[curr][j]%MOD+MOD) % MOD;
                //a[i][j] -= a[i][cur] * a[curr][j]%MOD;
                //a[i][j]%=MOD;
            }
            a[i][cur] = 0;
        }
        curr++;
        //print();
    }
    if (curr < n)
    {
        return 1;
    }
    return 2;
}
signed main()
{
    // cin>>n;
    scanf("%d", &n);
    int tt;
    // a
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    // 1
    for(int i=n;i<2*n;i++){
        a[i-n][i]=1;
    }
    // print();
    int t = solve();
    if (t == 0 || t==1)
    {
        printf("No Solution");
    }
    else
    {
        //print();
        for (int i = 0; i < n; i++)
        {
            for(int j=0;j<n;j++){
                printf("%d ",(a[i][j+n]%MOD+MOD)%MOD);
            }
            printf("\n");
        }
    }
    return 0;
}