题目链接:https://www.luogu.org/problemnew/show/P3390
时空限制 1000ms / 128MB

题目背景

矩阵快速幂

题目描述

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

输入格式

第一行,n,k;

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

输出格式

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

输入样例

2 1
1 1
1 1

输出样例

1 1
1 1

说明

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

解题思路

矩阵快速幂模板。矩阵快速幂见https://blog.csdn.net/lzyws739307453/article/details/90144987.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mat {
    ll m[105][105];
}ans, a;
int n, mod = 1e9 + 7;
Mat Mul(Mat x, Mat y) {
    Mat e;
    memset(e.m, 0, sizeof(e.m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            e.m[i][j] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++)
                e.m[i][j] = (e.m[i][j] + (x.m[i][k] * y.m[k][j]) % mod) % mod;
        }
    }
    return e;
}
int main() {
    ll k;
    scanf("%d%lld", &n, &k);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%lld", &a.m[i][j]);
    for (int i = 0; i < n; i++)
        ans.m[i][i] = 1;
    while (k) {
        if (k & 1)
            ans = Mul(ans, a);
        a = Mul(a, a);
        k >>= 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            printf("%lld ", ans.m[i][j]);
        printf("\n");
    }
    return 0;
}