Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Matrix Multiplication
Description 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 Input The input contains multiple test cases. Each test cases consists of some lines: - Line 1: Contains two integers
*K*(*K*< 1000) and*M*(0 ≤*M*≤ 10*K*), indicating the dimension of the matrix is*K*×*K*and*K*+*M*elements of the matrix are 1’s. - Lines 2 ~
*M*+ 1: Each contains two integers*i*and*j*(0 ≤*i*,*j*<*K*,*i*≠*j*), indicating the element in the (*i*+ 1)-th row and (*j*+ 1)-th column is 1.
All elements on the primary diagonal of the matrix are 1’s. Output For each test case output one line containing the number of elements that are 1’s in the 2006th power of the given matrix. Sample Input 3 4 1 2 2 1 0 1 0 2 Sample Output 7 Source POJ Monthly--2006.07.30, Static |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator