先来考虑一个弱化版，将操作改成异或
对集合建线性基，然后贪心即可
再回到此题
与非的性质是非常强的
NOT x=x NAND x
x AND y=NOT(x NAND y)
x OR y=(NOT x) NAND (NOT y)
x XOR y=((NOT x)AND y)OR(x AND (NOT y))
结论1：对于两个位置\(i,j\)，若对于集合内所有的数，第\(i\)位和第\(j\)位相同，则组合起来的数也相同
结论2：对于两个位置\(i,j\)，若对于集合内的任意两个数，第\(i\)位和第\(j\)位不同：对于其四种不同的\((0,0)(1,1)(0,1)(1,0)\)情况，组合起来的数除去这两位后，集合均相同
证明：
我们这样来构造线性基，第\(i\)位元素为\(\And_{k=1}^n(a_k[i]==1?a_k:NOT~a_k)\)，这样能使第\(i\)位元素为相等位为\(1\),否则为\(0\)
然后在组合时使用或操作即可
按结论2构造的方法构造线性基，然后贪心即可
原文：https://www.cnblogs.com/Grice/p/12600517.html