洛谷【P3908】异或之和

二进制前置技能：https://www.cnblogs.com/AKMer/p/9698694.html

题目传送门：https://www.luogu.org/problemnew/show/P3908

首先，异或是具有交换律和结合律的（自己推推就知道了）。

然后我就一直在想怎么统计每一位可能会出现多少个(1)……

其实这题很简单，某偶数异或该偶数加一就等于一。所以我们只需要处理有多少对这样的组合就行了……如果(n)是奇数，那么就有(frac{n}{2}+1)对（一个数异或(0)等于它本身，我们把(0)也强行拉进来）。所以答案就等于(frac{n}{2}+1)个(1)异或起来。如果(n)是偶数，我们先把(1)到(n-1)的答案算出来，再异或(n)就可以了。

时间复杂度：(O(1))

空间复杂度：(O(1))

代码如下：

#include <cstdio>
using namespace std;
#define ll long long

ll read() {
    ll x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

int main() {
    ll n=read(),ans=0;
    if(n&1)ans=((n/2)+1)&1;
    else ans=(((n-1)/2+1)&1)^n;//如上所述
    printf("%lld
",ans);
    return 0;
}