1、概念
在数学上,矩阵是指纵横排列的二维数据表格,最早来自于方程组的系数及常数所构成的方阵。这一概念由19世纪英国数学家凯利首先提出。由mn个数组成m行n列的数表称为一个m×n的矩阵,记作A。其中aij称为第i行j列的元素。
这里做一下与行列式的区别:行列式行和列数相同是一个数,矩阵行和列不一定相同是一个数表。
2、矩阵乘法
矩阵A(n×k)、B(k×m)相乘得一个n×m的C矩阵 (必须后一个矩阵的行数等于前一个矩阵的的列数才能相乘)
其中C中第i行第j列 Σ(k,p=1) aip*bpj
代码:
struct matrix { int n,m; int z[233][233]; matrix() { n=m=0; memset(z,0,sizeof(z)); } }; matrix operator*(const matrix &a,const matrix &b) { matrix c; c.n = a.n; c.m = b.m; for (int i=1;i<=c.n;i++) for (int j=1;j<=c.m;j++) for (int k=1;k<=a.m;k++) c.z[i][j] = c.z[i][j] + a.z[i][k] * b.z[k][j]; return c; }
3、矩阵加速
首先我们要明白一个矩阵的n次方可以用快速幂做 从而用logn的速度得出值
我们可以用矩阵求递推式加速(这样讲比较抽象)
例子:斐波那契数列
我们都知道斐波那契数列的f[n+1]=f[n]+f[n-1]
当我们用{f[n-1],f[n]}这个1×2的矩阵乘{1,1}
{1,0}
得到{f[n],f[n]+1}
我们设
m1 = {1,0};
m2 = {1,1}
{1,0}
得到m1 * ksm(m2,n-1) = [fn,fn-1]
从而在将O(n)化为O(logn)
4、矩阵性质
0A=0,A0=0
IA=A,AI=A (I(n)=1)
A(BC)=(AB)C
A(B+C)=AB+AC
(B+C)A=BA+CA