矩阵 - 源码之家

熟悉一下矩阵乘法。【摘自百度百科】

注意事项

当矩阵A的列数等于矩阵B的行数时，A与B可以相乘。

矩阵C的行数等于矩阵A的行数，C的列数等于B的列数。
乘积C的第m行第n列的元素等于矩阵A的第m行的元素与矩阵B的第n列对应元素乘积之和。

基本性质

乘法结合律： (AB)C=A(BC)． [2]
乘法左分配律：(A+B)C=AC+BC [2]
乘法右分配律：C(A+B)=CA+CB [2]
对数乘的结合性k(AB）=(kA)B=A(kB）．
转置 (AB)T=BTAT．
矩阵乘法一般不满足交换律 [3] 。

*注：可交换的矩阵是方阵。

由于矩阵具有乘法结合律，可以使用快速幂。

const int maxn=100;
struct matrix{
	int a[maxn][maxn];
    //单位矩阵就是t=1的情况。
	matrix(int t=0){
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;++i) a[i][i]=t;
	}
	friend inline matrix operator +(const matrix &a,const matrix &b){
		matrix c;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				c.a[i][j]=add(a.a[i][j],b.a[i][j]);
		return c;
	}
	friend inline matrix operator *(const matrix &a,const matrix &b){
		matrix c;
		for(int i=1;i<=n;++i)
			for(int k=1;k<=n;++k) if(a.a[i][k])
				for(int j=1;j<=n;++j)
					c.a[i][j]=add(c.a[i][j],mul(a.a[i][k],b.a[k][j]));
		return c;
	}
	friend inline matrix operator ^(const matrix &a,const matrix &b){
		matrix c(1);
		for(;b;b>>=1,a=a*a) if(b&1) c=c*a;
		return c;
	}
};

矩阵可以求斐波那契数列——

在斐波那契数列中，F0 = 0, F1 = 1, 并且Fn = F[n−1]+F[n-2] (n≥2).

它满足如下矩阵乘法。

Fn就是乘完后矩阵右上角或者左下角那个。

POJ3070：

#include<cstdio>
#include<cstring>
using namespace std;
const int N=2;
const int mod=10000;
int T;
inline int add(int a,int b){ return (a+b)>=mod ? a+b-mod : a+b;}
inline int mul(int a,int b){ return (long long)a*b%mod;}
struct matrix{
	int a[3][3];
	matrix(int t=0){
		memset(a,0,sizeof(a));
		if(t==1) a[1][1]=a[2][2]=1;
	}
	friend inline matrix operator*(matrix a,matrix b){
		matrix c;
		for(int i=1;i<=N;++i)
			for(int k=1;k<=N;++k)
				for(int j=1;j<=N;++j)
					c.a[i][j]=add(c.a[i][j],mul(a.a[i][k],b.a[k][j]));
		return c;
	}
	friend inline int operator^(matrix a,int b){
		matrix c(1);    //这里的c是单位矩阵
		for(;b;b>>=1,a=a*a) if(b&1) c=c*a;
		return c.a[1][2]%mod;
	}
};
int main(){
	matrix A;
	A.a[1][1]=A.a[2][1]=A.a[1][2]=1,A.a[2][2]=0;
	
	while(scanf("%d",&T)&&(T!=-1))
		printf("%d\n",A^T);
}

矩阵

注意事项

基本性质

相关推荐