Exclusive or

某人号 Sam 声称这是找规律题目。

HDU 2014。

给定 $n$，求：

$$\sum_{i=1}^{n-1}i\oplus (n-i)$$

$n\le10^{500}$。

注意到这样一件事情：$i\oplus(n-i)=2(\lfloor\frac{i}{2}\rfloor\oplus\lfloor\frac{n-i}{2}\rfloor)+[n\bmod 2]$。

于是，设 $f(n)=\sum\limits_{i=0}^n i\oplus(n-i)$，那么：

Case #1: $n$ 为偶数

此时设 $n=2k$，那么考虑 $f(k)$：这个值恰好是对于 $i=0\sim k$，有 $\sum\limits_i i\oplus(n-i)=2f(k)$。

同理可得后面的部分为 $2f(k-1)$。

于是 $f(n)=2(f(k)+f(k-1))$。

Case #2：$n$ 为奇数

同上，此时后面的部分就不是 $f(k-1)$ 而是 $f(k)$ 了，同时我们要补上后面的部分，于是有 $f(n)=4f(k)+n+1$。

最后记忆化一下，然后写一个高精度即可。