高斯消元
P3389 【模板】高斯消元法
这里使用的是高斯消元法，即变换成上三角矩阵后回代求解。代码：
#include<bits/stdc++.h>
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<0)return -x;
return x;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++)
cin>>a[i][j];
int r=1;
for(int i=1;i<=n;i++){
int h=r;
for(int j=r+1;j<=n;j++)
if(ab(a[j][i])>ab(a[h][i]))
h=j;
if(ab(a[h][i])<eps)continue;
swap(a[r],a[h]);
for(int j=i;j<=n+1;j++)a[r][j]/=a[r][i];
for(int j=r+1;j<=n;j++){
double x=a[j][i];
for(int k=i;k<=n+1;k++)
a[j][k]-=a[r][k]*x;
}
r++;
}
if(r<=n){
for(int i=r;i<=n;i++)
if(ab(a[i][n+1])>eps){
cout<<-1<<endl;
return 0;
}
cout<<0<<endl;
return 0;
}
for(int i=n;i>=1;i--){
ans[i]=a[i][n+1];
for(int j=i+1;j<=n;j++)
ans[i]-=a[i][j]*ans[j];
}
for(int i=1;i<=n;i++){
if(ab(ans[i])<0.005)ans[i]=0.0;
cout<<fixed<<setprecision(2);
cout<<"x"<<i<<"="<<ans[i]<<endl;
}
return 0;
}P4783 【模板】矩阵求逆
设单位矩阵为 $E$，要求解的矩阵为 $A$。
若 ，
那么
显然以上是易证的，读者可以尝试证明，这里直接给出代码：
#include<bits/stdc++.h>
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<=n;i++){
int maxn=a[i][i],l=i;
for(int j=i;j<=n;j++) if(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;j<=n;j++) (a[i][j]*=mul)%=mod,(b[i][j]*=mul)%=mod;
for(int j=1;j<=n;j++){
if(j==i) continue;
int mul=a[j][i];
for(int k=1;k<=n;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<=n;i++){
b[i][i]=1;
for(int j=1;j<=n;j++) cin>>a[i][j];
}
if(!gauss()) cout<<"No Solution";
else{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) cout<<b[i][j]<<" ";
cout<<"\n";
}
}
return 0;
} P3390 【模板】矩阵快速幂
把快速幂的乘法改成矩阵乘法即可，代码：
#include<bits/stdc++.h>
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<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;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;i<=n;i++) ans.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;i<=n;i++) for(int j=1;j<=n;j++) cin>>A.c[i][j];
qpow(k);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) cout<<ans.c[i][j]<<" ";
cout<<"\n";
}
return 0;
}
Comments NOTHING