程序设计在线评测(Online Judge)


问题 1030. -- Count the Number of Cycles

1030: Count the Number of Cycles

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 3
[提交][状态][讨论版]

题目描述

In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel, and is constructed using a sparse bipartite graph. LDPC codes are capacity-approaching codes, which means that practical constructions exist that allow the noise threshold to be set very close (or even arbitrarily close on the BEC) to the theoretical maximum (the Shannon limit) for a symmetric memory-less channel.
LDPC codes are defined by a sparse parity-check matrix. This parity-check matrix is often randomly generated and the elements in it are 0 or 1. If we want use LDPC codes, we should make the parity-check matrix have no cycles. When four vertices of the rectangle in the matrix are 1, we say that the matrix has one cycle. Now we want to know how many cycles are in the matrix.
For a given matrix, you are to count the number of cycles in the matrix.

输入

There are several test cases, each test case starts with a line containing two positive integers M and N. M and N is the size of the matrix (1<=M<=100, 1<=N<=100). Next follow a matrix which contains only number 0 and 1. The input will finish with the end of file.

输出

.   For each the case, your program will output the number of cycles in the given matrix on separate line.

样例输入

1 3
1 1 1
2 3
1 0 1
0 1 1
3 3
1 0 1
0 1 1
1 1 1

样例输出

0
0
2

提示

题意:如果一个01矩阵中有任何4个1分别在矩形的4个顶点上,则这4个1构成一个


四环。

给你一个大小为M×N的01矩阵,你需要求出矩阵中四环的数目。

本题是一道简单思维题,主要考核参赛选手的思维能力


暴力穷举,时间复杂度为n^4,会超时

分析知,将矩阵的2行进行向量点乘,如果结果s小于2,说明这2行不存在四环,


如果结果s大于等于2,则这2行的四环数目为C(2,S)

所以此题可以将各行两两一组进行点乘,然后将各组四环数目相加,即得到最后


答案。

复杂度为n^3。

来源

[提交][状态][讨论版]