矩阵快速幂

accedhy · 2018-07-18 08:04:42 · 个人记录

矩阵快速幂和乘法快速幂一样，不过不同的是，*这里变成了mul，同时还要知道矩阵乘法的性质：

1、矩阵乘法满足结合律，不满足交换律，即AB不等于BA，因为矩阵乘为A(mn)B(ns)=C(ms)，所以必定是有顺序的

2、新矩阵第i行第j列的数等于A矩阵第i行和B矩阵第j列逐一相乘的和，代码中为

        tp.map[i][j]+=a.map[i][k]*b.map[k][j](k是从1到n）

#include<cstdio>
#define ll long long
using namespace std;
ll n,k;
int mod=(1e+9)+7;
struct node
{
    ll map[201][201];
}a,ans;
node mul(node a,node b)
{
    node tp;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            tp.map[i][j]=0;//刚开始一定要将结构体里的数组清空，否则会出错

    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k)
                tp.map[i][j]=(tp.map[i][j]+(a.map[i][k]*b.map[k][j])%mod)%mod;
    return tp;
}
void quick(node a,ll p)
{
    for(int i=1;i<=n;++i)
        ans.map[i][i]=1;
    while(p)
    {
        if(p&1)
            ans=mul(ans,a);
        a=mul(a,a);
        p>>=1;
    }
}
int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            scanf("%lld",&a.map[i][j]);
    quick(a,k);
    for(int i=1;i<=n;++i,printf("\n"))
        for(int j=1;j<=n;++j)
            printf("%lld ",ans.map[i][j]%mod);//别忘了最后结果在%一次
}