P3390 【模板】矩阵快速幂

佚名 6年前 (2019-04-09) 随笔 1853人围观抢沙发百度已收录

题目背景

矩阵快速幂

题目描述

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入输出格式

输入格式：

第一行，n,k

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

输出格式：

输出A^k

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

没什么可分析的，就是一道板子题，嘤嘤嘤我刚看到还以为是A*K...........做了半天发现是A^K

矩阵快速幂并没有什么困难的地方，毕竟快速幂大家都会，其实这个代码这么长，无非就是定义了一次矩阵乘法的方式，在定义完之后就可以当普通数据来直接算了

代码如下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define mod 1000000007
using namespace std;
struct mat {
    long long m[101][101];
} a,e;
long long n,k;
mat cheng(mat A,mat B) {
    mat c;
    memset(c.m,0,sizeof c.m);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            for(int k=1; k<=n; ++k)
                c.m[i][j]=c.m[i][j]%mod+A.m[i][k]*B.m[k][j]%mod;
    return c;
}
mat quickpower(mat x,long long y) {
    mat anser=e;
    while(y!=0) {
        if(y&1)
            anser=cheng(anser,x);
        x=cheng(x,x);
        y/=2;
    }
    return anser;
}
int main() {
    scanf("%lld %lld",&n,&k);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            scanf("%lld",&a.m[i][j]);
    for(int i=1; i<=n; i++)
        e.m[i][i]=1;
    mat ans=quickpower(a,k);
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=n; ++j)
            printf("%lld ",ans.m[i][j]%mod);
        printf("\n");
    }
    return 0;
}