数列之异或

致敬每一个版本逆行者(指不找规律数位$DP\; O(log^2n)$写过的所有人)

这道题看似很难，但就是一个找性质$O(1)$速秒的题

思考对于任意一个奇数与它减一，它们的二进制可以表示为$ABC1$和$ABCD0$，这时候不管前面的位是多少，它们的异或和都是$0001$

所以对于所有的数$\in [1,n]$，我们只需要考虑它可以组出多少组$0001$就可以很快的找到答案了

考虑在最前面添加一个$0$(不会影响答案，任意数异或$0$还是它本身)

当$n$是奇数时，恰好可以凑出$\frac{n+1}{2}$组$0001$，这时候只要考虑组数的奇偶性就行了

当$n$是偶数时，可以凑出$\frac{n-1}{2}$组$0001$和一个单独的$n$，同样判断奇偶性求异或和就行了

if( n&1 )
    cout<<( ( ( n+1 )>>1 )&1 );
else
    cout<<( n^( ( ( n+1 )>>1 )&1 ) );