矩阵快速幂与递推式

104 阅读 0 评论 69 点赞

我是靠谱客的博主冷静蜜粉，这篇文章主要介绍矩阵快速幂与递推式，现在分享给大家，希望可以做个参考。

其实矩阵快速幂和快速幂取模在实质上是相同的，通过在幂指数的那部分快速幂，减少了时间复杂度。

在这里就不详细说明了，直接给出代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
#include<string.h>
#define NN 2
typedef long long ll; 
struct matrix  //设定为NN*NN的矩阵 
{
    ll mat[NN][NN];
};
matrix mutiplymat(matrix a,matrix b)
{
    matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(ll i=0;i<NN;i++)          //矩阵乘法 
        for(ll k=0;k<NN;k++)
            for(ll j=0;j<NN;j++)
                c.mat[i][j]=(c.mat[i][j]+(a.mat[i][k]%m)*(b.mat[k][j]%m))%m;
    return c;
}
matrix powerm(matrix a,ll b)
{
    matrix ans;
    for(ll i=0;i<NN;i++)
    {
        for(ll j=0;j<NN;j++)
        {
            if(i==j) ans.mat[i][j]=1;
            else ans.mat[i][j]=0;
        }
    }
    while(b>0)           //矩阵快速幂 
    {
        if(b%2==1)ans=mutiplymat(ans,a);
        a=mutiplymat(a,a);
		b>>=1;
    }
    return ans;
}