题目描述：Given a n × n matrix A and a positive integer k, find the sum S = A A² A³ … A^k

我们知道，计算一个n阶矩阵的k次幂的复杂度是(logk * n^3)，也就是说只需进行logk次的矩阵乘法。

例如求A^16

A^2 = A * A

A^4 = A^2 * A^2

A^8 = A^4 * A^4

A^16 = A^8 * A^8

只需要4次

下面就是怎样转化问题了

令 B= [

        [A A]
        [0 I]

      ]

则 B^k = [

           [A^k   A ... A^k]
           [0          I   ]

         ]

则矩阵B的k次方的有上角即为答案。

代码：

#include<iostream>
using namespace std;
int n, k, m, x[60][60], ans[60][60], n2;
void multi(int a[60][60], int b[60][60], int c[60][60])
{
    for(int i = 0; i < n2; i )
        for(int j = 0; j < n2; j )
        {
            int sum = 0;
            for(int k = 0; k < n2; k )
            {
                sum = b[i][k] * c[k][j];
                if (sum >= m)
                    sum %= m;
            }
            if ((a[i][j] = sum) >= m)
                a[i][j] %= m;
        }
}
void cpy(int a[60][60], int b[60][60])
{
    for(int i = 0; i < n2; i )
        for(int j = 0; j < n2; j )
            a[i][j] = b[i][j];
}
void judge(int key, int t[60][60])
{
    cpy(t, x);
    if (key == 1)
        return;
    int i = 1, j = 1, temp[60][60], nex[60][60];
    while(i * 2 <= key)
    {
        i *= 2;
        if (j % 2)
            multi(temp, t, t);
        else
            multi(t, temp, temp);
        j ;
    }
    if (j % 2)
        cpy(temp, t);
    else
        cpy(t, temp);
    if (key == i)
        return;
    judge(key - i, nex);
    multi(t, temp, nex);
}
int main()
{
    scanf("%d%d%d", &n, &k, &m);
    memset(x, 0, sizeof(x));
    for(int i = 0; i < n; i )
        for(int j = 0; j < n; j )
        {
            scanf("%d", &x[i][j]);
            x[i][j n] = x[i][j];
        }
    n2 = n * 2;
    for(int i = n; i < n2; i )
        x[i][i] = 1;
    judge(k, ans);
    for(int i = 0; i < n; i )
    {
        printf("%d", ans[i][n]);
        for(int j = n 1; j < n2; j )
            printf(" %d", ans[i][j]);
        putchar('\n');
    }
    return 0;
}