POJ 3233 Matrix Power Series (矩阵快速幂＋二分)

Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + A^k.

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10⁹) and m (m < 10⁴). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output the elements of S modulo m in the same way as A is given.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
struct matrix
{
    int m[55][55];
}a;

matrix multiply(matrix x, matrix y)
{
    matrix ans;
    memset(ans.m, 0, sizeof(ans.m));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(x.m[i][j])
                for(int k = 1; k <= n; k++)
                    ans.m[i][k] = (ans.m[i][k] + x.m[i][j] * y.m[j][k]) % m;
    return ans;
}

matrix add(matrix x, matrix y)
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            x.m[i][j] = (x.m[i][j] + y.m[i][j]) % m;
    return x;
}

matrix quickmod(matrix a, int p)
{
    matrix ans;
    memset(ans.m, 0, sizeof(ans.m));
    for(int i = 1; i <= n; i++)
        ans.m[i][i] = 1;
    while(p)
    {
        if(p & 1)
            ans = multiply(ans, a);
        p >>= 1;
        a = multiply(a, a);
    }
    return ans;
}

matrix solve(matrix a, int k)
{
    if(k == 1)
        return a;
    matrix ans;
    memset(ans.m, 0, sizeof(ans.m));
    for(int i = 1; i <= n; i++)
        ans.m[i][i] = 1;
    ans = add(ans, quickmod(a, k >> 1));
    ans = multiply(ans, solve(a, k >> 1));
    if(k & 1) //奇数
        ans = add(ans, quickmod(a, k));
    return ans;
}

int main()
{
    int k;
    scanf("%d %d %d", &n, &k, &m);
    matrix ans, a;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &a.m[i][j]);
    ans = solve(a, k);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j < n; j++)
            printf("%d ", ans.m[i][j]);
        printf("%d\n",ans.m[i][n]);
    }
}