学习笔记--矩阵相关

高斯消元

找出变量间关系

• 模板

 - 高斯-约当消元法

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
using namespace std;
const int maxn=103;
const double eps=1e-8;
int n;
double a[maxn][maxn],b[maxn];//a--系数 b--常数 
inline bool gs(){
	double rate;
	for(register int i=1;i<=n;i++){//消元 
		int k=i;
		for(register int j=i+1;j<=n;j++)
		   if(fabs(a[j][i])>fabs(a[k][i]))k=j;//选取最大做主元防止误差 
		if(fabs(rate=a[k][i])<eps)return 0;//主元无系数 无解 
		for(register int j=i;j<=n;j++)swap(a[i][j],a[k][j]);//将主元那一行换到第i行来 
		swap(b[i],b[k]); 
		for(register int j=i;j<=n;j++)a[i][j]=a[i][j]/rate;//将主元系数化为1 
		b[i]=b[i]/rate;
		for(register int k=1;k<=n;k++){
			if(k==i)continue;
			rate=a[k][i];
			for(int j=i;j<=n;j++)a[k][j]=a[k][j]-a[i][j]*rate;
			b[k]=b[k]-b[i]*rate;
		}
	}
	return 1;
}
int main(){
	scanf("%d",&n);
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=n;j++){
			scanf("%lf",&a[i][j]); 
		}
		scanf("%lf",&b[i]);
	}
	if(gs()==1){
		for(register int i=1;i<=n;i++)printf("%.2lf
",b[i]);
	}
	else{
		puts("No Solution");
	}
	return 0;
}

• 简单变式

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
const int maxn=13;
const double eps=1e-8;
double a[maxn][maxn],b[maxn][maxn],c[maxn];
int n;
inline void gs(){
	double rate;
	int mx;
	for(register int i=1;i<=n;i++){
		mx=i;
		for(register int j=i+1;j<=n;j++){
			if(fabs(b[j][i])>fabs(b[mx][i]))mx=j;
		}
		//if(fabs(rate=b[mx][i])<eps)return ;
		rate=b[mx][i];
		for(register int j=i;j<=n;j++){
			swap(b[i][j],b[mx][j]);
		}
		swap(c[i],c[mx]);
		for(register int j=i;j<=n;j++)b[i][j]=b[i][j]/rate;
		c[i]=c[i]/rate;
		for(register int k=1;k<=n;k++){
			if(k==i)continue;
			rate=b[k][i];
			for(register int j=i;j<=n;j++)b[k][j]=b[k][j]-b[i][j]*rate;
			c[k]=c[k]-c[i]*rate;
		}
	}
	return ;
}
int main(){
	scanf("%d",&n);
	for(register int i=1;i<=n+1;i++){
		for(register int j=1;j<=n;j++){
			scanf("%lf",&a[i][j]);
		}
	}
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=n;j++){
			b[i][j]=2*(a[i][j]-a[i+1][j]);	
			c[i]+=a[i][j]*a[i][j]-a[i+1][j]*a[i+1][j];
		}
	}
	gs();
	for(register int i=1;i<=n;i++){
		printf("%.3lf ",c[i]);
	}
	return 0;
}
 

• 期望&马尔可夫过程&&UVa 10828

  待填坑

• 异或

  待填坑

线性基

• 待填坑

矩阵加速递推

关键构造友矩阵

• 斐波那契数列

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#define ll long long 
using namespace std;
const int maxn=107;
const long long p=1000000007;
struct Matrix{
	int n,m;
	ll ma[maxn][maxn];
	Matrix(int rk){n=m=rk;for(register int i=1;i<=rk;i++)ma[i][i]=1;}
	Matrix(int rk_n,int rk_m){n=rk_n,m=rk_m;}
	Matrix(){;}
	Matrix operator *(const Matrix &x)const{
	   Matrix c=Matrix(n,x.m);
	   for(register int i=1;i<=n;i++){
	   	for(register int j=1;j<=x.m;j++){
	   		ll tmp=0;
	   		for(register int k=1;k<=m;k++){
	   			tmp+=ma[i][k]*x.ma[k][j];
	   			if(tmp>19260817)tmp=tmp%p;
			   }
			c.ma[i][j]=tmp;
		   }
	   }
	   return c;	
	}
	Matrix operator ^(const int &C)const{
		int c=C;
		Matrix ans=Matrix(n);
		Matrix res=*this;
		while(c){
			if(c&1){ans=ans*res;}
			res=res*res;
			c=c>>1;
		}
		return ans;
	}
	Matrix operator ^(const ll &C)const{
		ll c=C;
		Matrix ans=Matrix(n);
		Matrix res=*this;
		while(c){
			if(c&1){ans=ans*res;}
			res=res*res;
			c=c>>1;
		}
		return ans;
	}
};
int main(){
	ll n;
	Matrix f0(2,1);f0.ma[1][1]=1,f0.ma[2][1]=1;
	Matrix A(2);A.ma[1][1]=1,A.ma[1][2]=1,A.ma[2][1]=1,A.ma[2][2]=0;
	scanf("%lld",&n);
	if(n<=2){
		cout<<1<<endl;
		return 0;
	}
	//Matrix ans=mul(Matrix_ksm(A,n),f0);
	//Matrix ans=(A^(n-1))*f0;
    A=A^(n-1);
    Matrix ans=f0*A;
	printf("%lld
",ans.ma[1][1]);
	return 0; 
}
 

• 简单变式

  注意！！！矩阵定义中一定要加memset，否则可能有非0元素，太恶心了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#define ll long long 
const ll p=1000000007;
const int maxn=15;
int t;
struct Matrix{
	int n,m;
	ll ma[maxn][maxn];//注意！！！！一定要memset 
	Matrix(int _n){n=m=_n;memset(ma,0,sizeof(ma));for(register int i=1;i<=n;i++)ma[i][i]=1;}
	Matrix(int _n,int _m){n=_n,m=_m;}
	Matrix(){;}
	Matrix operator *(const Matrix& b)const {
		Matrix c=Matrix(n,b.m);
		for(register int i=1;i<=n;i++){
		  for(register int j=1;j<=b.m;j++){
		  	ll tmp=0;
		  	for(register int k=1;k<=m;k++){
		  		tmp+=ma[i][k]*b.ma[k][j];
		  		if(tmp>19260817)tmp=tmp%p;
			  }
			c.ma[i][j]=tmp;
		  }
	   }
		  return c;
	}
	Matrix operator ^(const int &C)const {
		int c=C;
		Matrix ans=Matrix(n);
		Matrix res=*this;
		while(c){
			if(c&1)ans=ans*res;
			res=res*res;
			c=c>>1;
		}
		return ans;
	}
	Matrix operator ^(const ll &C)const {
		ll c=C;
		Matrix ans=Matrix(n);
		/*for(int i=1;i<=3;i++){
		    for(int j=1;j<=3;j++)printf("%lld ",ans.ma[i][j]);
		    puts("");
	        }*/
		Matrix res=*this;
		while(c){
			if(c&1)ans=ans*res;
			res=res*res;
			c=c>>1;
			
		}
		return ans;
	}
};
int main(){
	ll n;
	scanf("%d",&t);
	while(t--){
		scanf("%lld",&n);
		if(n<=3){puts("1");continue;}
		Matrix A=Matrix(3,3);
		A.ma[1][1]=1;A.ma[1][2]=0;A.ma[1][3]=1;
		A.ma[2][1]=1;A.ma[2][2]=0;A.ma[2][3]=0;
		A.ma[3][1]=0;A.ma[3][2]=1;A.ma[3][3]=0;
		Matrix f0=Matrix(3,1);
		f0.ma[1][1]=1,f0.ma[2][1]=1,f0.ma[3][1]=1;
	    A=A^(n-1);
	    //std::cout<<'*'<<A.ma[1][1]<<std::endl;
	    /*for(int i=1;i<=3;i++){
		 for(int j=1;j<=3;j++)printf("%lld ",A.ma[i][j]);
		 puts("");
	    }*/
		f0=f0*A;
		printf("%lld
",f0.ma[1][1]);
	}
	return 0;
}

• 进阶

  https://www.luogu.org/problemnew/show/P1707 构造转移矩阵比较麻烦还要快速乘

  我的题解：https://www.cnblogs.com/Rye-Catcher/p/9089459.html

  https://www.luogu.org/problemnew/show/P2643

  待填坑

矩阵树定理（Matrix-Tree）

• 待填坑

  推荐阅读：http://www.cnblogs.com/zj75211/p/8039443.html

  完全二分图生成树的个数是
  　　
  (n^{m−1}*m^{n−1})

  bzoj2467 bzoj1002 SP3381