标题:二进制偶矩阵 出处:Felix021 时间:Sat, 30 Jun 2012 22:34:30 +0000 作者:felix021 地址:https://www.felix021.com/blog/read.php?2080 内容: 这是2012年百度实习招聘非技术类的某道笔试题。 给一个5×5的矩阵,每个元素只能是0或者1。 请问,有多少种不同的矩阵,能够满足每一行、每一列都有偶数个1? ==== 分割线 ==== 乍看这个题目,觉得是数学题。画了个5*5的矩阵,试图填几个数字进去看看是否可以推出一些结论。果断失败。 然后想了下,这题如果枚举的话,也就是2的25次方,大约3200万这个规模,不是很夸张。于是决定暴力搞一下。 最简单的做法就是for (i = count = 0; i < 2<<25 - 1; i++) check_even(i) && count++; 这个check_even(i)里头把 i 当成一个25bit的二进制数字,并转换为对应的5*5矩阵,判断其每一行和每一列是否满足要求。(p.s. whusnoopy的做法是直接使用位运算,更简单,不过思路就断了。。) 一个不难想到的优化是,在for之前先把每一行给枚举了,这样就不需要在check_even里面每次进行转换,只需要从 i 中取出对应的bits,就可以直接找到每一行。 更进一步,由于题目要求每一行都是偶数个1,所以可以进行剪枝——在枚举的时候只需要保留有偶数个1的情况就行了,枚举出5行,然后判断每个列。很容易计算,每行5个bit,偶数个1的情况是2^4=16种。于是需要枚举的矩阵数量降至16^5。 再进一步剪枝——题目要求所以列是偶数,那么在已经确定前4行的情况下,第5行是可以直接推出来的,需要枚举的矩阵数量降至16^4。但还需要做的事情是,判断第5行是否有偶数个1。 到了这一步,豁然开朗——因为很容易证明,第5行必然是偶数个1: 1) 每一列都是偶数个1(ABCDE都是偶数),所以矩阵中必然有偶数个1(F=A+B+C+D+E为偶数) 2) 前4行都是偶数个1(HIJK都是偶数),所以第5行必然是偶数个1(L=F-H-I-J-K为偶数) (p.s. 这个证明是WHUMSTC群里某同学给出的,非常清晰,所以我就不给我自己那个很挫的证明过程了) 于是开头的直觉获胜,问题的答案就是:16^4,也就是(2^4)^4。 ==== 分割线 ==== 扩展: 1. 如果矩阵的大小是 N×N ,甚至是 M×N 呢? 根据上述结论,很容易推知,对于M*N的矩阵,结果是2^((M-1) * (N-1))。 2. 如果要求满足每一行、每一列都有奇数个1呢?(whusnoopy提出) 这个结论就不那么直接了,对M*N有一定的限制。 Generated by Bo-blog 2.1.0