线性代数初步

高斯消元 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}