【矩阵乘法】逆矩阵

这东西很吼啊，

简介

有时遇到一些题目，要用到矩阵的前缀积+前缀逆矩阵，来计算区间的矩阵积，
逆矩阵和逆元差不多，两两相乘即可达到除效果，

待定系数法

直接设逆矩阵为a,b,c,d…，它与原矩阵相乘以后得出的矩阵是 除了对角线为1外，其余为0 的矩阵E，所以直接代入高斯消元解即可，

复杂度： O ( n 6 ) O(n^6) O(n6)

初等变换法

看一下高斯消元的所有操作：

1. 整一行乘上一个数
2. 整一行减去另一行
   我们发现，这些操作都可以用矩阵相乘的形式表示出来，
   所有，最标准的高斯消元，其实是可以表示为两矩阵相乘的样子的；
   而求逆矩阵正好是要求，这两个矩阵相乘以后，出来的矩阵只有对角线为1（E矩阵），

那么我们可以大胆的猜想，直接用高斯消元的思想，通过把每一行，乘上或除上某个数（逆元），把当前位变成1或0，这样就相当于求逆矩阵，
那我们怎么记录呢？
先开一个E矩阵，我们在对原来的矩阵操作时，也对这个矩阵做相同的操作，
比如：

1. 原矩阵整一行乘上一个数，这个矩阵也把这一行乘上这个数，
2. 原矩阵整一行减去另一行，比如行i-行j，这个矩阵也把行i-行j，

这样既可求出逆矩阵，简单明了，

Code

原矩阵a，求出的逆矩阵为b，

void GNI(int I)
{fo(i,0,M){if(!a[i][i])continue;LL t=ksm(a[i][i],mo-2);fo(j,0,M)a[i][j]=a[i][j]*t%mo,b[i][j]=b[i][j]*t%mo;fo(j,0,M)if(i!=j&&a[j][i]){t=a[j][i];fo(k,0,M){b[j][k]=(b[j][k]-b[i][k]*t)%mo;a[j][k]=(a[j][k]-a[i][k]*t)%mo;if(a[j][k]<0)a[j][k]+=mo;}}}
}

【矩阵乘法】逆矩阵

这东西很吼啊，

简介

有时遇到一些题目，要用到矩阵的前缀积+前缀逆矩阵，来计算区间的矩阵积，
逆矩阵和逆元差不多，两两相乘即可达到除效果，

待定系数法

直接设逆矩阵为a,b,c,d…，它与原矩阵相乘以后得出的矩阵是 除了对角线为1外，其余为0 的矩阵E，所以直接代入高斯消元解即可，

复杂度： O ( n 6 ) O(n^6) O(n6)

初等变换法

看一下高斯消元的所有操作：

1. 整一行乘上一个数
2. 整一行减去另一行
   我们发现，这些操作都可以用矩阵相乘的形式表示出来，
   所有，最标准的高斯消元，其实是可以表示为两矩阵相乘的样子的；
   而求逆矩阵正好是要求，这两个矩阵相乘以后，出来的矩阵只有对角线为1（E矩阵），

那么我们可以大胆的猜想，直接用高斯消元的思想，通过把每一行，乘上或除上某个数（逆元），把当前位变成1或0，这样就相当于求逆矩阵，
那我们怎么记录呢？
先开一个E矩阵，我们在对原来的矩阵操作时，也对这个矩阵做相同的操作，
比如：

1. 原矩阵整一行乘上一个数，这个矩阵也把这一行乘上这个数，
2. 原矩阵整一行减去另一行，比如行i-行j，这个矩阵也把行i-行j，

这样既可求出逆矩阵，简单明了，

Code

原矩阵a，求出的逆矩阵为b，

void GNI(int I)
{fo(i,0,M){if(!a[i][i])continue;LL t=ksm(a[i][i],mo-2);fo(j,0,M)a[i][j]=a[i][j]*t%mo,b[i][j]=b[i][j]*t%mo;fo(j,0,M)if(i!=j&&a[j][i]){t=a[j][i];fo(k,0,M){b[j][k]=(b[j][k]-b[i][k]*t)%mo;a[j][k]=(a[j][k]-a[i][k]*t)%mo;if(a[j][k]<0)a[j][k]+=mo;}}}
}