题目链接

构造的好题。表示是看了题解才会做的。

假如[l,r]长度不超过4，直接暴力就行了。

假如[l,r]长度大于等于5，那么如果k = 1，显然答案应该是l；如果k=2，可以找到a^(a+1)=1；如果k=3，首先只取两个就得到一个下界为1，但是可能出现为0的情况，下面再仔细讨论。如果k>=4，可以找到两组a^(a + 1) = 1，所以答案是0。

现在剩下的问题就是如何判断k=3的情况答案能否为0了。答案为0时我们只有可能取了3个数，设它们为x,y,z，并且不妨设有l <= z < y < x <= r。

我们考虑x的最高位非零位。这一位y必须是1，z必须是0，因为y > z并且它们的异或和为0。考虑接下来一位，假如z的这一位为0，我们可以将x,y的上一位变为0，这一位都变为1。注意到x,y,z仍然是满足条件的，因为x变小了，而z变大了，而x > y > z依然满足。最后，我们发现z的第一个非零位。我们将z后面的位全部填为1，x,y的前一位都为1，当前位x必为1，y必为0，后面我们将x全部填为0，y全部填为1。显然，x不会变大，z不会变小，并且x > y > z仍然满足。于是当且仅当存在这样构造的x,y,z时我们能够找到一组符合题意的x,y,z。我们注意到z = 2^k - 1，于是直接枚举z就行了。