题目链接

(模板)矩阵快速幂

题目背景

矩阵快速幂

题目描述

给定$n\times n$的矩阵$A$,求$A^k$。

输入格式

第一行两个整数$n,k$接下来$n$行,每行$n$个整数,第$i$行的第$j$的数表示$A_{i,j}$。

输出格式

输出$A^k$共$n$行,每行$n$个数,第$i$行第$j$个数表示$(A^k)_{i,j}$,每个元素对$10^9+7$取模。

样例输入

2 1
1 1
1 1

样例输出

1 1
1 1

说明/提示

【数据范围】
对于$100\%$的数据:$1\le n \le 100$,$0 \le k \le 10^{12}$,$|A_{i,j}| \le 1000$

题解

明显这是一道矩阵快速幂的板题,下面先介绍一下矩阵快速幂吧。
矩阵快速幂就是把矩阵乘法和快速幂结合一下。
对于矩阵的计算,这里就讲一下矩阵乘法,其他运算就不赘述了。
对于两个矩阵$A$,$B$,它们的行数和列数分别为$ax,ay,bx,by$。
要能进行$A \times B$,需要满足$ay=bx$,
$A \times B$的结果是矩阵$C$,$C$的行数和列数分别为$ax,by$,$C_{j,i}=\sum^{ay}_{k=1}A_{j,k}*B_{k,i}$。
也就是说$C$的第$i$行第$j$列等于$A$的第$i$行和$B$的第$j$列,各个对应的数的乘积的和。
关于快速幂的话想必大家都会了,那么我们只要定义一个$struct$来存储矩阵,然后重载一下运算符,就和普通的快速幂没有区别了。
如果不会重载运算符的话也可以写一个函数。
注意:因为中间有乘法,所以要开$long\ long$,还要记得取模,刚开始打的时候取模少了一个$0$,调了半天o(╥﹏╥)o
上代码:

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n;
long long k;
struct aa{
    long long a[109][109];
    aa operator * (aa x){
        aa uans;
        for(int j=1;j<=n;j++)
            for(int i=1;i<=n;i++){
                uans.a[j][i]=0;
                for(int p=1;p<=n;p++)
                    uans.a[j][i]=(uans.a[j][i]+a[j][p]*x.a[p][i]%mod)%mod;
            }
        return uans;
    }
};
aa ksm(aa x,long long p){
    aa uans;
    for(int j=1;j<=n;j++)
        for(int i=1;i<=n;i++)
            if(i==j) uans.a[j][i]=1;
            else uans.a[j][i]=0;
    while(p){
        if(p&1) uans=uans*x;
        x=x*x;
        p>>=1;
    }
    return uans;
}
int main(){
    scanf("%d%lld",&n,&k);
    aa a;
    for(int j=1;j<=n;j++)
        for(int i=1;i<=n;i++)
            scanf("%lld",&a.a[j][i]);
    aa ans=ksm(a,k);
    for(int j=1;j<=n;j++){
        for(int i=1;i<=n;i++)
            printf("%lld ",ans.a[j][i]);
        puts("");
    }
    return 0;
}