题目描述
求一个N×N的矩阵的逆矩阵。答案对10^9+7 +7取模。
输入格式
第一行有一个整数N,代表矩阵的大小;
从第2行到第N+1行,每行N个整数,其中第i+1行第j列的数代表矩阵中的元素aij 。
输出格式
若矩阵可逆,则输出N行,每行N个整数,其中第ii行第jj列的数代表逆矩阵中的元素 bij,答案对10^9+7取模;
否则只输出一行 No Solution。
(A,E)–>(E,A-1)
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=1e9+7;
const int maxn=410;
int n;
struct node
{
int a[maxn][maxn];
void init(void)
{
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
a[i][i]=1;
}
void input(void)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}
}
void _swap(int x,int y)
{
for(int i=1;i<=n;i++)
swap(a[x][i],a[y][i]);
}
void mul_k(int x,int k)
{
for(int i=1;i<=n;i++)
a[x][i]=(ll)a[x][i]*k%mod;
}
void mul_k_add(int x,int k,int y)
{
for(int i=1;i<=n;i++)
a[y][i]=((a[y][i]+(ll)a[x][i]*k)%mod+mod)%mod;
}
void print(void)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%d ",a[i][j]);
putchar('\n');
}
}
}a,b;
int mypow(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=(ll)ans*a%mod;
a=(ll)a*a%mod;
b>>=1;
}
return ans;
}
void get(void)
{
a.input();
b.init();
for(int i=1;i<=n;i++)
{
if(!a.a[i][i])
{
for(int j=i+1;j<=n;j++)
{
if(a.a[j][i])
{
a._swap(i,j);
b._swap(i,j);
break;
}
}
}
if(!a.a[i][i])
{
printf("No Solution\n");
return ;
}
b.mul_k(i,mypow(a.a[i][i],mod-2));
a.mul_k(i,mypow(a.a[i][i],mod-2));
for(int j=i+1;j<=n;j++)
{
b.mul_k_add(i,-a.a[j][i],j);
a.mul_k_add(i,-a.a[j][i],j);
}
}
for(int i=n;i>=1;i--)
{
for(int j=i-1;j>=1;j--)
{
b.mul_k_add(i,-a.a[j][i],j);
a.mul_k_add(i,-a.a[j][i],j);
}
}
b.print();
}
int main(void)
{
scanf("%d",&n);
get();
return 0;
}