每次选择时，由于剩下的数与正确答案的差的绝对值的和是一定的，那么两个cpu一定会选择同一位，填相反的数
也就是说，每次选择都会将集合划分为两个子集，且满足子集除了被选的位外各个位1的个数为子集大小的一半
这样的选择会进行k次，每一位都会被选择，所以最后每个数都会被等概率选到
排序之后，设sum[i]表示a[i]的前缀和，如果满足\(sum[i-1]<\lceil\frac{a[i]}{2}\rceil\) ，那么\((sum[i-1],\lceil \frac{a[i]}{2}\rceil)\)是不能覆盖的区间，且满足\((\lceil\frac{a[i]}{2}\rceil,sum[i])\)一定是合法区间
证明：
\([\lceil\frac{a[i]}{2}\rceil,a[i]]\)，\([\lceil \frac{sum[i]}{2}\rceil,sum[i]]\)分别合法
\(\lceil \frac{sum[i]}{2}\rceil<=a[i]\)时显然合法
\(\lceil \frac{sum[i]}{2}\rceil>a[i]\)时，我们要做的就是从sum[i]中不断拿出元素，使左边界小于等于a[i],且右边界始终在上一次移动前的左边界的右边
对于移动过程中的一个sum[x]和sum[x-1]，若\(sum[x-1]>=\lceil\frac{ sum[x]}{2}\rceil\)，这次移动合法，继续移动
若\(sum[x-1]<\lceil\frac{ sum[x]}{2}\rceil\)，化简
由刚才的结论知，此时满足区间\([\lceil \frac{a[x]}{2} \rceil,sum[x]]\)合法，因为\(a[x]<=a[i]\)，且移动到此时仍是合法，即在之前移动过程中没有断层，故区间\([\lceil\frac{a[i]}{2}\rceil,sum[i]]\)合法，移动结束
证毕
原文：https://www.cnblogs.com/sitiy/p/15172296.html