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:
A B A + B
0 0 0
0 1 1
1 0 1
1 1 1
Truth Table of Addition
A B AB
0 0 0
0 1 0
1 0 0
1 1 1
Truth Table of Multiplication
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:
Line 1: Contains two integers K (K < 1000) and M (0 ¡Ü M ¡Ü 10K), 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.
For each test case output one line containing the number of elements that are 1¡¯s in
the 2006th power of the given matrix.
POJ Monthly--2006.07.30, Static