Matrix Power Series

时间限制：

1000 ms  |  内存限制：65535 KB

难度：

4

 

描述

Given a 

n × 

n matrix 

A and a positive integer 

k, find the sum 

S = 

A + 

A

² + 

A

³ + … + 

A^k.

 

输入

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

输出

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

样例输入

2 2 40 11 1

样例输出

1 22 3

来源

上传者

#include 
     
      #include 
      
       using namespace std;int M=1000007;struct Matrix{    long int line,column;    long int m[40][40];};struct Matr{    long int line,column;    long int m[70][70];    Matr(Matrix x){        line =x.line*2;        column=x.column*2;        for(int i=0;i
       
        >=1;    }    return an;}int main(){    int n,m,k;    Matrix a;    scanf("%d %d %d",&n,&k,&m);    M=m;    a.line=n;    a.column=n;    for(int i=0;i