主要思路
这道题还蛮妙的,自己比较顺利的思考出来了。
考虑设置前缀异或和\(\{ S_i \}\),根据异或按位处理的性质,显然对于所有的\(S_i\)都会小于\(2^n\)。最后,我们可以把限制变成:
- 不存在两个相同的前缀和。
- 不存在一对前缀和,其异或值为\(x\)。
针对\(x\)的大小关系,我们可以分成两种情况:
- \(x \geq 2^n\),不存在一对\((S_i, S_j)\)的异或为\(x\),因为存在更高的位并不会被消除。
- \(x < 2^n\),我们发现每选择一个数作为前缀和,整个\(2^n\)中就会少一个对应的可以被选择的数。所以,我们每次选一个作为\(S_i\)的数时,都要把\(S_i xor \ x\)打标记。
结合一下就可以了。