Matrix Power Series(行列の和を求める:S(k))
1372 ワード
http://poj.org/problem?id=3233
Matrix Power Series
Time Limit: 3000 MS
メモリLimit: 131313722 K
Total Submissions: 28970
Acceepted: 11777
Description
Given a n × n matrix A and a positive integer k,find the sum S = A + A 2 + A 3 + … + 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).The n follow n lineach containing n nonnegative integers below 32,768,giving A’s elemens in row-majer order.
Output
Output the elements of S modulo m in the same way as A is given.
Sample Input
この問題は一つの行列の和式を求めます.S(k)、直接対和式に対して配達します.
マトリクスを作成します.ここでSとAは2*2のマトリクスです.Eは単位行列、Oはゼロ行列(全部0です.他のマトリックスと掛け合わせても0です.)を表します.明らかにE、Oは2*2です.
Matrix Power Series
Time Limit: 3000 MS
メモリLimit: 131313722 K
Total Submissions: 28970
Acceepted: 11777
Description
Given a n × n matrix A and a positive integer k,find the sum S = A + A 2 + A 3 + … + 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).The n follow n lineach containing n nonnegative integers below 32,768,giving A’s elemens in row-majer 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 11 2
2 3この問題は一つの行列の和式を求めます.S(k)、直接対和式に対して配達します.
マトリクスを作成します.ここでSとAは2*2のマトリクスです.Eは単位行列、Oはゼロ行列(全部0です.他のマトリックスと掛け合わせても0です.)を表します.明らかにE、Oは2*2です.
