|Online Judge||Problem Set||Authors||Online Contests||User|
Many studies have been done on developing efficient algorithms to calculate matrix multiplication. But it remains as a hard topic today. In this problem you are to calculate the 2006th power of a square Boolean matrix where addition and multiplication are defined as follows:
Let A be a square matrix. The zeroth power of A is the identity matrix. The n-th (n > 0) power of A is the product of A and its (n − 1)-th power.
The input contains multiple test cases. Each test cases consists of some lines:
All elements on the primary diagonal of the matrix are 1’s.
For each test case output one line containing the number of elements that are 1’s in the 2006th power of the given matrix.
3 4 1 2 2 1 0 1 0 2
POJ Monthly--2006.07.30, Static
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator