题目描述

给定n×n矩阵A和正整数k，求和S=A+A2+A3+…+Ak。

输入格式
输入只包含一个测试用例。

第一行输入包含三个正整数n，k和m。

接下来n行，每行包含n个非负整数（均不超过32,768），用以描绘矩阵A。

输出格式
按与描述矩阵A相同的方式，输出将S中所有元素对m取模后得到的矩阵。

数据范围
1≤n≤30,
1≤k≤109,
1≤m<104

样例

输入样例:
2 2 4
0 1
1 1
输出样例：
1 2
2 3

算法1

矩阵逐步的相乘然后相加是不可以的 太慢
但是矩阵也有类似快速幂的做法

/*
A + A^2 =A(I+A)

A + A^2 + A^3 + A^4 = (A + A^2)(I + A^2)
记做sum(n) = A +A^2 +A^3 +…+A^n
如果n是偶数 sum(n) = sum(n/2)(I+A^(n/2))
如果n是奇数 sum(n) = sum(n-1) + A^n
= sum((n-1)/2)(I+A^((n-1)/2)) + A^n
*/

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;


struct matrix {
    int data[35][35];
};

int n = 0;
int m = 0;
int k = 0;

//矩阵乘法
matrix mul(matrix a, matrix b)
{
    matrix c;
    memset(c.data, 0, sizeof(c.data));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                c.data[i][j] = (c.data[i][j] + 1ll * a.data[i][k] * b.data[k][j]) % m;
            }
        }
    }

    return c;
}

//矩阵加法
matrix add(matrix a, matrix b) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a.data[i][j] = (a.data[i][j] + b.data[i][j])%m;
        }
    }
    return a;
}

//矩阵快速幂
matrix quickpow(matrix a, int k) {
    matrix  c;
    memset(c.data, 0, sizeof(c.data));
    for (int i = 1; i <= n; i++)
        c.data[i][i] = 1;
    while (k) {
        if (k & 1) c = mul(c, a);
        k >>= 1;
        a = mul(a, a);
    }
    return c;
}

//正式计算 sum k
matrix sum(matrix a, int k) {
    if (k == 1) return a;
    matrix c;
    memset(c.data, 0, sizeof(c.data));
    for (int i = 1; i <= n; i++)
        c.data[i][i] = 1;
    c = add(c, quickpow(a, k >> 1));
    c = mul(c, sum(a, k >> 1));
    if (k & 1) c = add(c, quickpow(a, k));
    return c;
}




/*
A + A^2 =A(I+A)

A  + A^2 + A^3 + A^4 = (A + A^2)(I + A^2)
记做sum(n) = A  +A^2 +A^3 +...+A^n
如果n是偶数  sum(n) = sum(n/2)(I+A^(n/2))
如果n是奇数  sum(n) = sum(n-1) + A^n
            = sum((n-1)/2)(I+A^((n-1)/2)) + A^n
*/

int main()
{
    matrix mat;
    cin >> n;
    cin >> k;
    cin >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> mat.data[i][j];
        }
    }

    matrix ret = sum(mat, k);



    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << ret.data[i][j] << " ";
        }
        cout << endl;
    }
}