矩阵快速幂模板+例题（快速入门）

￡神魔★判官ぃ 2023-07-18 02:38 12阅读 0赞

# 矩阵快速幂模板+例题（快速入门） #

本来早在一个月前就应该把这给掌握的，硬是得等到卡题了，才想到来补知识

### 文章目录 ###

*  矩阵快速幂模板+例题（快速入门）
 *   *  模板
     *  例题
     *   *  一、HDU 1575：Tr A
         *  二、POJ 3070：Fibonacci
         *  三、HNUCM 1620: Fy's dota2

## 模板 ##

[传送门：矩阵快速幂基础讲解][Link 1]

单纯的求某一矩阵的快速幂是没有什么意义的，主要是由于所求的递推式的数比较大时，如果使用暴力递推，必定会超时，这时矩阵快速幂的作用就完美体现了

根据个人码风和编码习惯，敲了一份模板，如果觉得有用，大佬们不妨留个赞呗（手动滑稽）

/*
     *  矩阵快速幂 n*n矩阵的x次幂
     */
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #define ll long long
    #define mod 9973
    using namespace std;
    int n,x;
    const int maxn=15;
    struct mat{
        
        ll m[maxn][maxn];
        mat(){
        
            memset(m,0,sizeof(m));
        }
        //重载矩阵乘法
        mat operator * (const mat b)const{
        
            mat ans;
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=n;j++){
        
                    for(int k=1;k<=n;k++){
        
                        ans.m[i][j]+=m[i][k]*b.m[k][j];
                        ans.m[i][j]%=mod;
                    }
                }
            }
            return ans;
        }
    };
    //矩阵快速幂
    mat pow_mat(mat a,int b){
        
    mat ans;
    //初始化为单位矩阵
        for(int i=1;i<=n;i++){
        
            ans.m[i][i]=1;
        }
        while(b){
        
            if(b&1){
        
                ans=ans*a;
            }
            a=a*a;
            b>>=1;
        }
        return ans;
    }
    int main(){
        
        int t;
        scanf("%d",&t);
        while(t--){
        
            scanf("%d%d",&n,&x);
            mat a;
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=n;j++){
        
                    scanf("%lld",&a.m[i][j]);
                }
            }
            a=pow_mat(a,x);
            //输出矩阵
            /*
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    cout<<a.m[i][j]<<" ";
                }
                cout<<endl;
            }*/
            ll sum=0;
            for(int i=1;i<=n;i++){
        
                sum=(sum+a.m[i][i])%mod;
            }
            printf("%lld\n",sum);
        }
        return 0;
    }

## 例题 ##

### 一、HDU 1575：Tr A ###

[题目链接][Link 2]

**题目大意：**  
题意也是很简单，毕竟是模板题嘛；求某一矩阵a的k次幂，之后求矩阵对角线的和取模

**代码：**  
刚刚我的模板恰好是解决这一题的完整代码

### 二、POJ 3070：Fibonacci ###

[题目链接][Link 3]

**题目大意：**  
求最经典的斐波拉契数列f\[n\]，但由于n比较大，如果我们直接使用递归的话会超时，但是我们选择用数组存的话，内存肯定会超限（因为n过于大）

这时就得想到矩阵快速幂了  
![在这里插入图片描述][20200323162610750.png]  
**代码：**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #define inf 0x3f3f3f3f
    #define mod 10000
    #define ll long long
    using namespace std;
    const double eps=1e-6;
    const int maxn=5;
    ll n,x;
    struct mat{
        
        ll m[maxn][maxn];
        mat(){
        
            memset(m,0,sizeof(m));
        }
        mat operator * (const mat b)const{
        
            mat ans;
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=n;j++){
        
                    for(int k=1;k<=n;k++){
        
                        ans.m[i][j]+=m[i][k]*b.m[k][j];
                        ans.m[i][j]%=mod;
                    }
                }
            }
            return ans;
        }
    };
    mat pow_mat(mat a,int b){
        
        mat ans;
        for(int i=1;i<=n;i++){
        
            ans.m[i][i]=1;
        }
        while(b){
        
            if(b&1){
        
                ans=ans*a;
            }
            a=a*a;
            b>>=1;
        }
        return ans;
    }
    int main(){
        
        n=2;
        while(~scanf("%lld",&x)){
        
            if(x==-1)
                break;
            mat a;
            a.m[1][1]=1,a.m[1][2]=1;
            a.m[2][1]=1,a.m[2][2]=0;
            a=pow_mat(a,x);
            printf("%lld\n",a.m[1][2]);
        }
        return 0;
    }

### 三、HNUCM 1620: Fy’s dota2 ###

[题目链接][Link 4]

**题目大意：**  
很明显能够得到递推公式：  
![在这里插入图片描述][20200323163127568.png_pic_center]  
由于所求的数列下标比较大，于是用到快速幂，构造矩阵  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70_pic_center]  
**代码：**

#include<bits/stdc++.h>
    #define inf 0x3f3f3f3f
    #define mod 7777777
    #define ll long long
    using namespace std;
    const double eps=1e-6;
    const int maxn=15;
    int n,x;
    struct mat{
        
        ll m[maxn][maxn];
        mat(){
        
            memset(m,0,sizeof(m));
        }
        //重载矩阵乘法
        mat operator * (const mat b)const{
        
            mat ans;
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=n;j++){
        
                    for(int k=1;k<=n;k++){
        
                        ans.m[i][j]+=m[i][k]*b.m[k][j];
                        ans.m[i][j]%=mod;
                    }
                }
            }
            return ans;
        }
    };
    //矩阵快速幂
    mat pow_mat(mat a,int b){
        
        mat ans;
        for(int i=1;i<=n;i++){
        
            ans.m[1][i]=pow(2,n-i);
        }
        while(b){
        
            if(b&1){
        
                ans=ans*a;
            }
            a=a*a;
            b>>=1;
        }
        return ans;
    }
    int main(){
        
        scanf("%d%d",&n,&x);
        if(n>=x){
        
            printf("%d\n",(int)pow(2,x-1));
        }
        else{
        
            mat a;
            for(int i=1;i<=n;i++){
        
                a.m[i][1]=1;
                a.m[i][i+1]=1;
            }
            a=pow_mat(a,x-n);
            printf("%lld\n",a.m[1][1]);
        }
        return 0;
    }

[Link 1]: https://www.cnblogs.com/cmmdc/p/6936196.html
[Link 2]: http://acm.hdu.edu.cn/showproblem.php?pid=1575
[Link 3]: http://poj.org/problem?id=3070
[20200323162610750.png]: /images/20230528/67598a2914ef42c48288c2ac9d9f7e66.png
[Link 4]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?id=1620
[20200323163127568.png_pic_center]: /images/20230528/e26a1c86a33d4f4fb297cea0f750ead8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/d49386a92f5f42fb9c672b984153068d.png