编程介的小学生 2016-12-26 03:30 采纳率: 20.5%
浏览 1166
已采纳

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:

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.

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 ≤ 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.

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

  • 写回答

1条回答 默认 最新

  • threenewbee 2016-12-29 15:31
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥50 汇编语言除法溢出问题
  • ¥65 C++实现删除N个数据列表共有的元素
  • ¥15 Visual Studio问题
  • ¥15 state显示变量是字符串形式,但是仍然红色,无法引用,并显示类型不匹配
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗