学步园

/*

 由于对二分的不熟练，这道题不知坑了多久... 
 这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。
 比如，当k=6时，有： A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)
 应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。

*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cmath>
using namespace std;
struct Matrix
{
    int a[32][32];
}a1;
int n,k,mod;
Matrix mult2(Matrix A,Matrix B){ /// 矩阵乘法
    Matrix C;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            C.a[i][j]=0;
            for(int k=0;k<n;k++){
                C.a[i][j] += A.a[i][k]*B.a[k][j];
                C.a[i][j] %= mod;
            }
        }
    }
    return C;
}

Matrix add(Matrix A,Matrix B){ /// 矩阵加法
    Matrix C;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            C.a[i][j] = (A.a[i][j]+B.a[i][j])%mod;
        }
    }
    return C;
}

Matrix pow(Matrix a,int k){ /// 二分矩阵快速幂
    if(k == 1)return a;
    if(k % 2)return mult2(pow(a,k-1),a);
    return pow(mult2(a,a),k/2);
}

Matrix sum(int k){ /// 二分快速求和
    if(k<= 1)  return a1; 
    if(k % 2)  return add(sum(k-1) , pow(a1,k));
    else{
        Matrix temp = sum(k/2);
        return add(temp , mult2(temp,pow(a1,k/2)));
    }
}
int main()
{
    int i,j;
    scanf("%d%d%d",&n,&k,&mod) ;
    for(i =0; i < n;i++)
        for(j =0 ;j < n;j++)
            scanf("%d",&a1.a[i][j]);
    Matrix ans;
    ans = sum(k);
    for(i =0 ;i< n;i++) {
        for(j=0 ;j < n - 1;j++)
            printf("%d ",ans.a[i][j]);
        printf("%d\n",ans.a[i][j]);
    }
    return 0;
}
/*

2 2 4
0 1 
1 1

*/