poj 3233 矩阵快速幂

地址 http://poj.org/problem?id=3233

大意是n维数组 最多k次方  结果模m的相加和是多少

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

Sample Input

2 2 4
0 1
1 1

Sample Output

1 2
2 3

题解

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

/*
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
*/

代码如下

#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;
    }
}