矩阵

线性代数的计算：

其中cij为a中第i竖列与b中第j横行对应乘积的合

如：c11=a11*b11+a21*b12+…+an1*b1n

cij=a1i*bj1+a2i*bj2+…+ani*bjn

矩阵：

对于上述计算中的集合a，b，我们可以称之为矩阵

矩阵乘法：

f(n)=f(n-1)+f(n-2)

这个是我们所熟知的斐波那契数列

在我们已知f(1),f(2)的情况下要求f(n)的值

一般来说，我们会直接从第一个算到第n个，这是传统思路

现在暂时忘记这种方法，假设我们有矩阵A

满足[f(n-1),f(n-2)]*A=[f(n),f(n-1)]

由于f(n)=f(n-1)+f(n-2)

所以可以写成：[f(n-1),f(n-2)]*A=[f(n-1)+f(n-2),f(n-1)]

用线性代数求出

矩阵A=

1 1

1 0

代码实现：

a[ ][ ],b[ ][ ],tmp[ ][ ]表示三个矩阵的值，n表示行列

const int N=10;

int tmp[N][N];

void multi(int a[][N],int b[][N],int n)

{

    memset(tmp,0,sizeof tmp);

    for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)

    for(int k=0;k<n;k++)

        tmp[i][j]+=a[i][k]*b[k][j];

    for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)

        a[i][j]=tmp[i][j];

}

计算会把矩阵a的值改变为结果，直接取a的值即可

当然，这种程度的代码实用性不高，和递推的复杂度一样都是O（n）

矩阵快速幂：

稍微温习一下普通快速幂

pow(int a,int b,int c)  a底数，b次方，对c取模

{

int ret=0;

while(b)

{

   if(b&1)

   ret=(ret*a)%mod;

   a=a*a;

b>>=1

}

}

将这个思想运用到矩阵当中便是矩阵快速幂：

int res[N][N];

void Pow(int a[][N],int n)

{

    memset(res,0,sizeof res);//n是幂，N是矩阵大小

    for(int i=0;i<n;i++) res[i][i]=1;

    while(n)

    {

        if(n&1)

            multi(res,a,N);//res=res*a; （此处用到的multi是上面计算矩阵的函数）

        multi(a,a,N);//a=a*a

        n>>=1;

    }

}