题解 P4783 【【模板】矩阵求逆】
这是一道线性代数的好题
调死我这个大菜鸡了
如果您还不太清楚线性代数的话，那么我可以跟您讲一个笑话：
有人在盘点世界上吊死人最多的树
据说是美国还是法国的哪片森林里的
其实这完全是瞎扯
他们怕是不知道，有一种叫做“线性代数”的树
上面吊死的人远比那些树多得多
嗯嗯，笑话讲完了，我们来做题吧qwq
在看这篇题解之前，需要了解的芝士：
1.高斯-约旦消元法
2.矩阵的基本知识（矩阵的初等变换，单位矩阵等等）
应该都好理解的吧（至于我为什么不用高斯消元，是因为我个人认为，高斯消元的精度不是很高，代码有些长 所以不好背 ）
首先来讲一讲什么是矩阵求逆
题目告诉我们一个矩阵\(A\),让我们求得一个矩阵\(B\)，使得\(AB=BA=I\)。
那么问题来了，这个矩阵\(I\)是个smg？
矩阵\(I\)就是传说中的单位矩阵
这是一个\(4\times4\)的单位矩阵
\[I=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix} \]看到了嘛，单位矩阵就是一条对角线上都是1，余都为0的矩阵。
说白了，就是求\(B=I/A\)这个东西
可惜好像矩阵运算里没有除法
我上面那个表达式也是不合法的
然后我们就会用BFS（Baidu First Search）去找思路
求逆思路：
1.把\(A\)和它等大的单位矩阵\(I\)放在一个矩阵里
2.对\(A\)进行高斯消元使\(A\)化成单位矩阵
3.此时原来单位矩阵转化成逆矩阵
意不意外？惊不惊喜？
知道了具体的过程，我们就可以来搞事情了，把P3389的程序复制粘贴过来……
然后修改一下，加上右边的矩阵\(I\)，修改一下输出，然后……
\({\color{Red}WA}\)
是我沙雕了……两个题目的数据类型都不一样啊啊啊啊啊啊啊
高斯消元是\(Double\)的，但是这道题……\(long\;long\)……
还带着除法……
所以话说乘法逆元是个好东西
然后把数据类型改一下，写个龟速幂套乘法逆元，然后……
\({\color{Red}WA}\)
嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤嘤……
然后我借鉴了一下题解，发现是%运算的锅，因为这个很可能出现负数，然后就会\({\color{Red}WA}\)掉。
比如我的\({\color{green}AC}\)程序里有这个：
a[j][k]=(a[j][k]%mod+mod)%mod;
和之前\({\color{red}WA}\)这个：
a[j][k]%=mod;
是不一样的。
上面的那个确保了没有负数（Maybe）
所以说，%这个运算最好用在膜拜管理员/神仙/巨佬中，如果题目里有模数，那么……我多半会挂掉……
\({\color{green}AC}\)程序：
#include
using namespace std;
const long long mod=1e9+7;
long long a[500][1000];
long long IE(long long m,long long n)
{
long long p=1;
while(n)
{
if(n%2==1) p=(p*m)%mod;
m=m*m%mod;
n/=2;
}
return p%mod;
}
int main()
{
long long n;
cin>>n;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
cin>>a[i][j];
for(int i=1; i<=n; i++) a[i][i+n]=1;
for(int i=1; i<=n; i++)
{
int tx=i;
for(int j=i+1; j<=n; j++)
if(abs(a[j][i])>abs(a[tx][i])) tx=j;
if(i!=tx)
{
for(int j=1; j<=n*2; j++)
swap(a[i][j],a[tx][j]);
}
if(!a[i][i])
{
cout<<"No Solution";
return 0;
}
int I=IE(a[i][i],mod-2);
for (int j=1; j<=n; j++)
if(j!=i)
{
long long t=a[j][i]*I%mod;
for (int k=i; k<=n*2; k++)
{
a[j][k]-=a[i][k]*t;
a[j][k]=(a[j][k]%mod+mod)%mod;
}
}
for(int j=1; j<=2*n; j++)
a[i][j]=a[i][j]*I%mod;
}
for(int i=1; i<=n; i++)
{
for(int j=n+1; j<=n*2; j++)
cout< 就是这样子吧……线性代数真的是毒瘤……喵喵喵~~~