矩阵快速幂求递推式

用矩阵将快速幂可以以logn级别的时间复杂度求出递推式

典型题：求斐波那契数列第n项  n<=2^31-1 ；显然 ，一步一步递推o（n）算法效率不够

0 1 0　　　　f[n-3]　　f[n-2]

0 0 1　　*　 f[n-2] =　f[n-1]

1 1 3　　　　f[n-1]　　f[n-3]+f[n-2]+3*f[n-1]   

在方阵右上方  n-1  * n-1  矩阵的主对角线上 填1  最下面一行  从右到左填  递推式的系数  

用矩阵实现递推式

由矩阵的基本性质知  A^n  *P =A^（n-1） *A*P

所以求递推式第n项  可以通过* 转移矩阵  n次实现

那么问题来了  A^n  如何快速求？

可以用二分法递归求，也可以用二进制累乘法

下面介绍二进制快速幂:

2^11=2^1  *  2^2  *  2^8

也就是按照11的二进制1011   加权算

代码如下：

while(p)
        {
            if(p&1) ans=multi(ans,b); //p是要求的幂次   矩阵ans 初始状态是单位矩阵（相当于数1）
            b=multi(b,b);　　　　　　　　//矩阵b是转移矩阵
            p>>=1;　　　　　　　　　　　　//右移迭代
        }
//  A^n    最终结果就是矩阵     ans

　　

对于 转移矩阵  *  递推首项  可以把递推首项 设置为方阵 第一列有值，其余列为0

这样只用方阵乘法就够了

matrix multi(matrix a,matrix b)
{
    matrix ans;
    memset(ans.a,0,sizeof(ans.a));
    for(int i=0;i<maxn;i++)
        for(int j=0;j<maxn;j++)
            for(int k=0;k<maxn;k++){
                ans.a[i][j]+=a.a[i][k]*b.a[k][j];
                ans.a[i][j]%=m;
            }
    return ans;
}

　　

以下是矩阵快速幂求递推式的模板代码  HDU1757

#include <bits/stdc++.h>
using namespace std;
const int maxn =10;
//矩阵结构体
struct matrix
{
    int a[maxn][maxn];
};
matrix a,b;
int a0[15],k,m;
void init()
{
    memset(b.a,0,sizeof(b.a));
    for(int i=0;i<9;i++)
        b.a[i][i+1]=1;
    for(int i=0;i<10;i++)
        b.a[9][i]=a0[9-i];
    for(int i=0;i<10;i++)
        a.a[i][0]=i;
}
matrix multi(matrix a,matrix b)
{
    matrix ans;
    memset(ans.a,0,sizeof(ans.a));
    for(int i=0;i<maxn;i++)
        for(int j=0;j<maxn;j++)
            for(int k=0;k<maxn;k++){
                ans.a[i][j]+=a.a[i][k]*b.a[k][j];
                ans.a[i][j]%=m;
            }
    return ans;
}
int main()
{
    while(scanf("%d%d",&k,&m)!=EOF)
    {
        for(int i=0;i<10;i++)
            scanf("%d",&a0[i]);
        init();
        int p=k-9;
        matrix ans;
        memset(ans.a,0,sizeof(ans.a));
        for(int i=0;i<10;i++)
            ans.a[i][i]=1;
        while(p)
        {
            if(p&1) ans=multi(ans,b);
            b=multi(b,b);
            p>>=1;
        }
        ans=multi(ans,a);
        cout<<ans.a[9][0]<<endl;
    }
    return 0;
}