矩阵求逆

约 4 个字 56 行代码 预计阅读时间 1 分钟

const int N=402,mod=1e9+7;
int a[N][N],ih[N],jh[N];//a,1-index
bool inverseMatrix(int n)
{
    for(int k=1;k<=n;++k)
    {
        for(int i=k;i<=n && !ih[k];++i)
        {
            for(int j=k;j<=n;++j)
            {
                if(!a[i][j])
                    continue;
                ih[k]=i;
                jh[k]=j;
                break;
            }
        }
        if(!ih[k])
            return false;
        for(int j=1;j<=n;++j)
            swap(a[k][j],a[ih[k]][j]);
        for(int i=1;i<=n;++i)
            swap(a[i][k],a[i][jh[k]]);
        if(!a[k][k])
            return false;
        a[k][k]=inv(a[k][k]);
        for(int i=1;i<=n;++i)
        {
            if(i!=k)
                a[k][i]=(ll)a[k][i]*a[k][k]%mod;
        }
        for(int i=1;i<=n;++i)
        {
            if(i==k)
                continue;
            for(int j=1;j<=n;++j)
            {
                if(j!=k)
                    a[i][j]=(a[i][j]+(ll)(mod-a[i][k])*a[k][j])%mod;
            }
        }
        for(int i=1;i<=n;++i)
        {
            if(i!=k)
                a[i][k]=(ll)(mod-a[i][k])*a[k][k]%mod;
        }
    }
    for(int k=n;k;--k)
    {
        for(int j=1;j<=n;++j)
            swap(a[k][j],a[jh[k]][j]);
        for(int i=1;i<=n;++i)
            swap(a[i][k],a[i][ih[k]]);
    }
    return true;
}