线性代数初步

2026年1月16日 ooliver OI

高斯消元

P3389 【模板】高斯消元法

这里使用的是高斯消元法，即变换成上三角矩阵后回代求解。代码：

#include
using namespace std;
const int N=55;
const double eps=1e-8;
int n;
double a[N][N],ans[N];
double ab(double x){
	if(x>n;
	for(int i=1;i>a[i][j];
	int r=1;
	for(int i=1;iab(a[h][i]))
				h=j;
		if(ab(a[h][i])eps){
				cout=1;i--){
		ans[i]=a[i][n+1];
		for(int j=i+1;j

`#include
using namespace std;
const int N=55;
const double eps=1e-8;
int n;
double a[N][N],ans[N];
double ab(double x){
	if(x0)return -x;
	return x;
}
int main(){
	cin>>n;
	for(int i=1;i
		for(int j=1;j1;j++)
			cin>>a[i][j];
	int r=1;
	for(int i=1;i
		int h=r;
		for(int j=r+1;j
			if(ab(a[j][i])>ab(a[h][i]))
				h=j;
		if(ab(a[h][i])continue;
		swap(a[r],a[h]);
		for(int j=i;j1;j++)a[r][j]/=a[r][i];
		for(int j=r+1;j
			double x=a[j][i];
			for(int k=i;k1;k++)
				a[j][k]-=a[r][k]*x;
		}
		r++;
	}
	if(r
		for(int i=r;i
			if(ab(a[i][n+1])>eps){
				cout1
				return 0;
			}
		cout0
		return 0;
	}
	for(int i=n;i>=1;i--){
		ans[i]=a[i][n+1];
		for(int j=i+1;j
			ans[i]-=a[i][j]*ans[j];
	}
	for(int i=1;i
		if(ab(ans[i])0.005)ans[i]=0.0;
		coutsetprecision(2);
		cout"x""="ans[i]
	}
	return 0;
}`

P4783 【模板】矩阵求逆

设单位矩阵为 $E$ ，要求解的矩阵为 $A$ 。若 A 一定变换→ EA \ \underrightarrow{一定变换} \ E，那么 E 同样变换→ A−1E \ \underrightarrow{同样变换} \ A^{-1} 显然以上是易证的，读者可以尝试证明，这里直接给出代码：

#include
using namespace std;
#define int long long

const int N=405;
const int mod=1e9+7;
int n,ans;
int a[N][N],b[N][N];

int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1) (res*=x)%=mod;
		(x*=x)%=mod,y>>=1;
	}
	return res%mod;
}

int gauss(){
	for(int i=1;imaxn) maxn=a[j][i],l=j;
		if(maxn==0) return 0;
		swap(a[i],a[l]);
		swap(b[i],b[l]);
		int mul=qpow(a[i][i],mod-2);
		for(int j=1;j>n;
	for(int i=1;i>a[i][j];
	}
	if(!gauss()) cout

`#include
using namespace std;
#define int long long

const int N=405;
const int mod=1e9+7;
int n,ans;
int a[N][N],b[N][N];

int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1) (res*=x)%=mod;
		(x*=x)%=mod,y>>=1;
	}
	return res%mod;
}

int gauss(){
	for(int i=1;i
		int maxn=a[i][i],l=i;
		for(int j=i;jif(a[j][i]>maxn) maxn=a[j][i],l=j;
		if(maxn==0) return 0;
		swap(a[i],a[l]);
		swap(b[i],b[l]);
		int mul=qpow(a[i][i],mod-2);
		for(int j=1;ja[i][j]*=mul)%=mod,(b[i][j]*=mul)%=mod;
		for(int j=1;j
			if(j==i) continue;
			int mul=a[j][i];
			for(int k=1;k
				a[j][k]=((a[j][k]-((a[i][k]*mul)%mod))%mod+mod)%mod;
				b[j][k]=((b[j][k]-((b[i][k]*mul)%mod))%mod+mod)%mod;
			}
		}
	}
	return 1;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i
		b[i][i]=1;
		for(int j=1;j>a[i][j];
	}
	if(!gauss()) cout"No Solution";
	else{
		for(int i=1;i
			for(int j=1;jb[i][j]" ";
			cout"\n";
		}	
	}
	return 0;
} `

P3390 【模板】矩阵快速幂

把快速幂的乘法改成矩阵乘法即可，代码：

#include
using namespace std;
#define int long long

const int N=105;
const int mod=1e9+7;
int n,k;
struct matrix{
	int c[N][N];
	matrix(){memset(c,0,sizeof c);}
}ans,A;
matrix operator*(matrix &x,matrix &y){
	matrix tmp;
	for(int i=1;i>=1;
	}
}

signed main(){
	cin>>n>>k;
	for(int i=1;i>A.c[i][j];
	qpow(k);
	for(int i=1;i

`#include
using namespace std;
#define int long long

const int N=105;
const int mod=1e9+7;
int n,k;
struct matrix{
	int c[N][N];
	matrix(){memset(c,0,sizeof c);}
}ans,A;
matrix operator*(matrix &x,matrix &y){
	matrix tmp;
	for(int i=1;i
		for(int j=1;j
			for(int k=1;k
				(tmp.c[i][j]+=x.c[i][k]*y.c[k][j]%mod)%=mod;
			}
		}
	}
	return tmp;
}

void qpow(int k){
	for(int i=1;ians.c[i][i]=1;
	while(k){
		if(k&1) ans=ans*A;
		A=A*A,k>>=1;
	}
}

signed main(){
	cin>>n>>k;
	for(int i=1;ifor(int j=1;j>A.c[i][j];
	qpow(k);
	for(int i=1;i
		for(int j=1;jans.c[i][j]" ";
		cout"\n";
	}
	return 0;
}`

P1962 斐波那契数列

[FiFi+1]∗[1110]=[Fi+1Fi+Fi+1]=[Fi+1Fi+2]\begin{bmatrix} F_i & F_{i+1} \end{bmatrix}

\begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}

= \begin{bmatrix} F_{i+1} & F_{i}+F_{i+1} \end{bmatrix}

= \begin{bmatrix} F_{i+1} & F_{i+2} \end{bmatrix}