洛谷【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\n",ans);
    return 0;
}

洛谷【P3908】异或之和

原文：https://www.cnblogs.com/AKMer/p/9713693.html