POJ3233 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和m，求S（上面有，复制粘贴格式错误，QAQ）（每个元素对m取模）

---

思路：
（第一次做根本就没有思路好吧，想了半天没搞懂，搜了搜博客，看到这张图秒懂QAQ）

来自https://www.cnblogs.com/sj-gank/p/11771343.html

 E是单位矩阵；

看完应该都是秒懂的吧QAQ

虽然实现还是花了很久，各种找bug。

---

AC代码：

#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=30;
int mod=10000;
ll T,n,k;
struct matrix{
    ll a[maxn][maxn];
    matrix(){
        memset(a,0,sizeof(a));
    }
};
struct Matrix{
    matrix b[2][2];
    Matrix(){
        memset(b,0,sizeof(b));
    }
};
matrix mul(matrix a,matrix b){
    matrix res;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j])%mod;
    return res;
}
matrix add(matrix a,matrix b){
    matrix res;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
                res.a[i][j] = (a.a[i][j] + b.a[i][j])%mod;
    return res;
}
Matrix mul(Matrix a,Matrix b){
    Matrix res;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                res.b[i][j] = add(res.b[i][j] , mul(a.b[i][k] , b.b[k][j]));
    return res;
}
matrix qpow(matrix A,ll m){//方阵A的m次幂
    matrix ans;
    for(int i=0;i<n;i++)
            ans.a[i][i]=1; //单位矩阵
    while(m){
        if(m&1)ans=mul(ans,A);
        A=mul(A,A);
        m>>=1;
    }
    return ans;
}
Matrix qpow(Matrix A,ll m){
    Matrix ans;
    for(int i=0;i<2;i++)
        for(int j=0;j<n;j++)
            ans.b[i][i].a[j][j]=1; //单位矩阵

    while(m){
        if(m&1)ans=mul(ans,A);
        A=mul(A,A);
        m>>=1;
    }
    return ans;
}
Matrix M;
int main()
{
    cin>>n>>k>>mod;
    matrix A;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>M.b[0][0].a[i][j];
    for(int i=0;i<n;i++){
        M.b[0][1].a[i][i]=1;
        M.b[1][1].a[i][i]=1;
    }
    Matrix res=qpow(M,k+1);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j){
                if(res.b[0][1].a[i][j]==0)
                    cout<<mod-1<<' ';
                else
                    cout<<res.b[0][1].a[i][j]-1<<' ';
            }else
                cout<<res.b[0][1].a[i][j]<<' ';
        }
        cout<<endl;
    }
}