原题

Solution

引理1：当 n > 6 n>6 n>6时全用 a n d and and能使最小值为 0 0 0

1 1 1个 a n d and and能使 1 1 1的个数减半，而 1 1 1个数最多 32 32 32个 1 1 1，所以 6 6 6个数能使 1 1 1的个数为 0 0 0

引理2： x o r xor xor操作能被 a n d and and操作代替

0^0=0；0&~0=0
0^1=1；0&~1=0
1^0=1；1&~0=1
1^1=0；1&~1=0
比较左右两列，发现 a n d and and操作一定 &lt; = x o r &lt;=xor <=xor操作

引理3：只用 a n d and and一定能得到最优解

把 n n n个数二进制展开，可以得到一个大小为 n ∗ 64 n*64 n∗64的表：
( 011101010101010 ) 2 (011101010101010)_2 (011101010101010)2​
( 100110101010100 ) 2 (100110101010100)_2 (100110101010100)2​
( 100101111010111 ) 2 (100101111010111)_2 (100101111010111)2​
把它竖着看，每列看作一个状态，不管用什么运算符，相同状态的最终结果一定相同
首先假设状态数大于 2 n 2^n 2n，因为状态数 &lt; = 2 n &lt;=2^n <=2n时三种操作都可以做到 0 0 0
用 a n d and and可以得到只有一个状态最终结果为 1 1 1
要证明的就是 o r or or、 x o r xor xor、 a n d and and三种操作混合不能使 2 n 2^n 2n种不同状态均为 0 0 0
假设有一个长度为 k k k的 01 01 01序列，每两个数之间的操作相同，注意到不管是哪种操作，最终结果都是 0 0 0或 1 1 1（且都能取到），于是长度为 n n n的混合序列可以看作若干个这样的序列（相当于缩点），最终结果是 0 0 0或 1 1 1（都能取到）

只用引理1已经能过了这题，但时间复杂度为 O ( n ∗ 6 n ) O(n*6^n) O(n∗6n)，引理2能优化到 O ( n ∗ 4 n ) O(n*4^n) O(n∗4n)，引理3能优化到 O ( n ∗ 2 n ) O(n*2^n) O(n∗2n)

Code

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int T,n,i,s;
ll a[101],ans,t;
int main(){
	for (scanf("%d",&T);T--;){
		scanf("%d",&n);
		for (i=0;i<n;i++) scanf("%llu",&a[i]);
		if (n>6){
			puts("0");
			continue;
		}
		ans=~0;
		for (s=0;s<1<<n;s++,ans=min(ans,t))
			for (i=0,t=~0;i<n;i++) t&=(s&(1<<i)?a[i]:~a[i]);
		printf("%llu\n",ans);
 	}
}