poj3233

maksyuki 发表于 oj 分类,标签: ,
0

Matrix Power Series

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

Source

POJ Monthly--2007.06.03, Huang, Jinsong

 

题目类型:矩阵快速幂 + 二分

算法分析:直接计算每一个矩阵的幂然后求和取模会TLE,此时考虑到A ^ 1 + A ^ 2 + A ^ 3 + A ^ 4 = (A ^ 1 + A ^ 2) + (A ^ 1 + A ^ 2) * A ^ 2,可以使用二分的思想先将A ^ 1 + A ^ 2 + ……A ^ n划分成{A ^ 1 + A ^ 2 + A ^ (k / 2)} + A ^(k / 2)] + {A ^ (k / 2 + 1) + A ^ + ……A ^ n}三部分,由于第三部分可以由第一部分每一项乘以A ^ (k / 2)得到,所以可以先计算出第一部分,再直接乘方求和