【矩阵乘法】逆矩阵

这东西很吼啊,

简介

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

待定系数法

直接设逆矩阵为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;
			}
		}
	}
}
    原文作者:HOWARLI
    原文地址: https://blog.csdn.net/HOWARLI/article/details/75207797
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞