解题思路

我们要在一个 $N\times M$ 的矩阵中，为每一行选择“原样(0)”或“整行反转(1)”这两种状态，使得对所有列，同一列上的 $N$ 个数字两两不同。 把每一行的选择记为布尔变量 $x_i\in\{0,1\}$（0=不翻转，1=翻转）。对于任意两行 $i,k$ 与任意一列 $j$，如果在某个组合下两行在列 $j$ 的值相等，则该组合被禁止：

• $A_{i,j}=A_{k,j}$ ⇒ 禁止 $(x_i=0,\ x_k=0)$
• $A_{i,j}=A_{k,M+1-j}$ ⇒ 禁止 $(0,1)$
• $A_{i,M+1-j}=A_{k,j}$ ⇒ 禁止 $(1,0)$
• $A_{i,M+1-j}=A_{k,M+1-j}$ ⇒ 禁止 $(1,1)$