一、矩阵的基础知识
1.结合性 （AB)C=A(BC）．
2.对加法的分配性 （A+B)C=AC+BC，C(A+B）=CA+CB ．
3.对数乘的结合性 k(AB）=（kA)B =A(kB）．
4.关于转置 (AB)'=B'A'．
一个矩阵就是一个二维数组，为了方便声明多个矩阵，我们一般会将矩阵封装一个类或定义一个矩阵的结构体，我采用的是后者。
最特殊的矩阵应该就是单位矩阵e了，它的对角线的元素为1，非对角线元素为0。一个n*n的矩阵的0次幂就是单位矩阵。
若A为n×k矩阵，B为k×m矩阵，则它们的乘积AB(有时记做A·B)将是一个n×m矩阵。其乘积矩阵AB的第i行第j列的元素为：
一般矩阵乘法采用朴素的O(n^3)的算法，但是对于一些比较稀疏的矩阵（就是矩阵中0比较多），对于这样的矩阵我们可以采用矩阵的优化，这个算法也适用于一般的矩阵，0特别多时，复杂度可能会降低到O(n^2)，实现如下：
还要注意的是，我们要尽可能的减少取模运算，因为取模的复杂度很高，这样我们就可以节约时间了。
矩阵加法就是简单地将对应的位置的两个矩阵的元素相加。
我们一般考虑的是n阶方阵之间的乘法以及n阶方阵与n维向量（把向量看成n×1的矩阵）的乘法。矩阵乘法最重要的性质就是满足结合律，同时它另一个很重要的性质就是不满足交换率，这保证了矩阵的幂运算满足快速幂取模（A^k % MOD）算法，矩阵快速幂其实就是二分指数，避免重复的计算。我们可以采用递归的方式很容易的写出来，但是当指数比较大，或者矩阵比较大得时候，我们就会出现栈溢出的状况，不断RE（我就被坑过）。所以还是写成迭代的方式比较好。
制作矩阵图一般要遵循以下几个步骤：
1、列出质量因素：
2、把成对对因素排列成行和列，表示其对应关系
3、选择合适的矩阵图类型
4、在成对因素交点处表示其关系程度，一般凭经验进行定性判断，可分为三种：关系密切、关系较密切、关系一般（或可能有关系)，并用不同符号表示
5、根据关系程度确定必须控制的重点因素
6、针对重点因素作对策表。
二、矩阵快速幂的应用
7、poj3070 是求解菲波那切数列，f(n)=f(n-1)+f(n-2),如果我们一个个递推求解，当n特别大的时候复杂度就会变的很高，对于f(n)= a*f(n-1)+b*f(n-2),在矩阵运算中我们会发现这样一组公式：
到知道这个公式后我们就采用矩阵快速幂的方法可以求解f(n)
[cpp]
#include
#include
#include
using namespace std;
struct mat{
int at[2][2];
};
mat d;
int n,mod;
mat mul(mat a,mat b)
{
mat t;
memset(t.at,0,sizeof(t.at));
for(int i=0;i
for(int k=0;k
if(a.at[i][k])
for(int j=0;j
t.at[i][j]+=a.at[i][k]*b.at[k][j];
if(t.at[i][j]>=mod){t.at[i][j]%=mod;}
}
}
}
return t;
}
mat expo(mat p,int k)
{
if(k==1)return p;
mat e;
memset(e.at,0,sizeof(e.at));
for(int i=0;i
while(k)
{
if(k&1)e=mul(p,e);
p=mul(p,p);
k>>=1;
}
return e;
}
int main()
{
n=2;mod=10000;
d.at[1][1]=0;
d.at[0][0]=d.at[1][0]=d.at[0][1]=1;
int k;
while(~scanf("%d",&k))
{
if(k==-1)break;
mat ret=expo(d,k);
int ans=ret.at[0][1]%mod;
printf("%d\n",ans);
}
return 0;
}
#include
#include
#include
using namespace std;
struct mat{
int at[2][2];
};
mat d;
int n,mod;
mat mul(mat a,mat b)
{
mat t;
memset(t.at,0,sizeof(t.at));
for(int i=0;i
for(int k=0;k
if(a.at[i][k])
for(int j=0;j
t.at[i][j]+=a.at[i][k]*b.at[k][j];
if(t.at[i][j]>=mod){t.at[i][j]%=mod;}
}
}
}
return t;
}
mat expo(mat p,int k)
{
if(k==1)return p;
mat e;
memset(e.at,0,sizeof(e.at));
for(int i=0;i
while(k)
{
if(k&1)e=mul(p,e);
p=mul(p,p);
k>>=1;
}
return e;
}
int main()
{
n=2;mod=10000;
d.at[1][1]=0;
d.at[0][0]=d.at[1][0]=d.at[0][1]=1;
int k;
while(~scanf("%d",&k))
{
if(k==-1)break;
mat ret=expo(d,k);
int ans=ret.at[0][1]%mod;
printf("%d\n",ans);
}
return 0;
}
2、poj3233题意：给出矩阵A，求S = A + A^2 + A^3 + … + A^k 二分和
[cpp]
#include
#include
#include
using namespace std;
#define LL long long
int n,m,k;
int MOD;
struct mat {
int at[40][40];
};
mat d;
mat mul(mat a, mat b)
{
mat ret;
memset(ret.at,0,sizeof(ret.at));
for (int i=0;i
for (int k=0;k
if(a.at[i][k])
for (int j=0;j
ret.at[i][j]+=a.at[i][k]*b.at[k][j];
if(ret.at[i][j]>=MOD){r