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

点击打开链接

Matrix Power Series

Description

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

Input

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

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

题目大意：

给定一个 n*n  的矩阵和一个整数 k,，要求的是S =  A + A² + A³ +
… + A^k.

出的是 S%Mod

解题思路：

首先这是一个矩阵的快速幂，将A^{k 用矩阵的快速幂求解出来（可以套模板），}

^{可以推出以下结论}

S_k = A + A² + A³ + … + A^k   

    =(1+A^k/2)*(A + A² + A³ + … + A^k/2  )+(A^k )

    =(1+A^k/2)*(S_k/2 )+(A^k )

然后可以递归啦，首先计算的是(1+A^k/2)，

^{这里的 1 不仅是 1 它是一个单位矩阵，然后递归一下，最后判断一下奇偶性}

^{要是偶数的时候就不用+(Ak )，要是奇数的话就+(Ak )，具体详见代码：}

#include <iostream>
#include <cstring>
using namespace std;
typedef struct Mar
{
    int m[40][40];
    void Init()///初始化为单位矩阵
    {
        memset(m, 0, sizeof(m));
        for(int i=0; i<40; i++)
            m[i][i] = 1;
    }
} Martrix;

int n, Mod;

Martrix Add(Martrix a, Martrix b)///矩阵加法
{
    Martrix c;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            c.m[i][j] = (a.m[i][j] + b.m[i][j]) % Mod;///一定要模 Mod
    return c;
}
Martrix Multi(Martrix a, Martrix b)///矩阵乘法
{
    Martrix c;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            c.m[i][j] = 0;
            for(int k=0; k<n; k++)
                c.m[i][j] += (a.m[i][k]*b.m[k][j])%Mod;///一定要模 Mod，将数值减小
            c.m[i][j] %= Mod;
        }
    }
    return c;
}
Martrix quick_mod(Martrix a, int b)///矩阵的快速幂
{
    Martrix ans;
    ans.Init();
    while(b)
    {
        if(b & 1)
            ans = Multi(ans, a);
        b>>=1;///二分
        a = Multi(a, a);
    }
    return ans;
}
Martrix Get_sum(Martrix a, int k)///递归
{
    if(k == 1)
        return a;
    Martrix ans;
    ans.Init();
    ans = Add(ans, quick_mod(a, k>>1));///1+A^(k/2)
    ans = Multi(ans,Get_sum(a,k>>1));///剩下的
    if(k & 1)///判断奇偶性
        ans = Add(ans,quick_mod(a,k));
    return ans;
}
int main()
{
    int k;
    while(cin>>n>>k>>Mod)
    {
        Martrix a;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin>>a.m[i][j];
        Martrix ans = Get_sum(a,k);
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n-1; j++)
                cout<<ans.m[i][j]<<" ";
            cout<<ans.m[i][n-1]<<endl;
        }
    }
    return 0;
}