poj3233(Matrix Power Series)快速幂

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

Input

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

Output

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

Sample Input

2 2 4
0 1
1 1

Sample Output

1 2
2 3

题意:给定矩阵A,求 S = A + A2 + A3 + … + Ak


题解:设S = I + A + A2 + A3 + … + Ak-1

快速幂计算即可


#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;

int n, k, m;

mat mul(mat& a, mat& b)
{
    mat c(2*n, vec(2*n));
    for (int i = 0; i < 2*n; ++i)
        for (int k = 0; k < 2*n; ++k)
            for (int j = 0; j < 2*n; ++j)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % m;
    return c;

}

mat pow(mat& a, int k)
{
    mat b(2*n, vec(2*n));
    for (int i = 0; i < 2*n; ++i)
        b[i][i] = 1;
    while (k > 0)
    {
        if (k&1)
            b = mul(b, a);
        a = mul(a, a);
        k >>= 1;
    }
    return b;
}

int main()
{
    cin >> n >> k >> m;
    mat A(2*n, vec(2*n));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            scanf("%d", &A[i][j]);
        A[n+i][i] = A[n+i][n+i] = 1;
    }
    A = pow(A, k+1);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            int a = A[n+i][j] % m;
            if (i == j)
                a = (a + m - 1) % m;
            printf("%d%c", a, j+1==n?'\n':' ');
        }
    return 0;
}



算法码上来 文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。

全部评论

相关推荐

有趣的牛油果开挂了:最近这个阶段收到些杂七杂八的短信是真的烦
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务