洛谷 P3390 ——————矩阵快速幂

ゝ一世哀愁。 2022-05-09 10:42 133阅读 0赞

## P3390 【模板】矩阵快速幂 ##

#### 题目背景 ####

矩阵快速幂

#### 题目描述 ####

给定 n ∗ n n\*n n∗n的矩阵A，求 A k A^k Ak

输入输出格式  
输入格式：  
第一行，n,k

第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素

#### 输出格式： ####

输出A^k

共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7

#### 输入样例\#1： ####

2 1  
1 1  
1 1

#### 输出样例\#1： ####

1 1  
1 1

#### 说明 ####

n<=100, k<=10^12, |矩阵元素|<=1000 算法：矩阵快速幂

--------------------

矩阵快速幂模板题：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int INF = 0x3f3f3f3f;
    const int MAXN= 110;
    const int MOD=1e9+7;
    ll b_n=0;
    ll N;
    ll C[MAXN];
    ll h[MAXN];
    struct mat{
        ll m[MAXN][MAXN]; };
    
    mat mul(mat a,mat b)
    {
        
            mat tmp;
            for(int i=1;i<=N;i++)
                    for(int j=1;j<=N;j++)
                    {
        
                            tmp.m[i][j]=0;
                            for(int k=1;k<=N;k++)
                                    tmp.m[i][j]=(tmp.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
                    }
            return tmp;
    }
    mat pow_mod(mat a,ll n)
    {
        
            mat ans;
            for(int i=1;i<=N;i++)
                    for(int j=1;j<=N;j++)
                            ans.m[i][j] = (i==j);
            while(n)
            {
        
                    if(n&1) ans=mul(ans,a);
                    a=mul(a,a);
                    n>>=1;
            }
            return ans;
    }
    int main()
    {
        
            ll n,k;
            while(~scanf("%lld %lld",&n,&k))
            {
        
                    mat b;
                    N=n;
                    for(int i=1;i<=n;i++)
                            for(int j=1;j<=n;j++)
                                    scanf("%lld",&b.m[i][j]);
                    mat a=pow_mod(b,k);
                    for(int i=1;i<=n;i++)
                    {
        
                            for(int j=1;j<=n;j++)
                            {
        
                                    if(j!=1)        printf(" ");
                                    printf("%lld",a.m[i][j]);
                            }
                            printf("\n");
                    }
            }
            return 0;
    }