题意：
定义
求(f(n),n leq 10^{500})
分析：
这个数列对应OEIS的A006582
先上公式：
递推的思路就是虽然不知道两个数的异或值，但是如果知道这两个数的奇偶性那么结果的奇偶性也就知道了。
还有一个公式：(2a oplus 2b = 2(a oplus b))，这个也很容易理解。
下面开始证明：
- (n=2k+1)时：
(; ; ; ; sumlimits_{i=1}^{n-1}(ioplus (n-i)))
(=2sumlimits_{i=1}^{k}((2i) oplus (n-2i)))
(=2sumlimits_{i=1}^{k}((2i) oplus (2k-2i+1)))
(=2sumlimits_{i=1}^{k}((2i) oplus (2k-2i) + 1))
(=2sumlimits_{i=1}^{k}((2i) oplus (2k-2i)) + 2k)
(=4sumlimits_{i=1}^{k}((i) oplus (k-i)) + 2k)
(=4sumlimits_{i=1}^{k-1}((i) oplus (k-i)) + 4(k oplus (k-k)) + 2k)
(=4f(k)+6k)
- (n-2k)时：
(; ; ; ; sumlimits_{i=1}^{n-1}(ioplus (n-i)))
(=sumlimits_{i=1}^{k-1}((2i) oplus (n-2i)) + sumlimits_{i=0}^{k-1}((2i+1) oplus (n-2i-1)))
(; ; ; ; sumlimits_{i=1}^{k-1}((2i) oplus (n-2i)))
(=sumlimits_{i=1}^{k-1}((2i) oplus (2k-2i)))
(=2sumlimits_{i=1}^{k-1}(i oplus (k-i)))
(=2f(k))
(; ; ; ; sumlimits_{i=0}^{k-1}((2i+1) oplus (n-2i-1)))
(=sumlimits_{i=0}^{k-1}((2i) oplus (2k-2i-2)))，两边都是奇数，把末位的(1)去掉后异或值不变
(=2sumlimits_{i=0}^{k-1}i oplus (k-1-i))
(=2sumlimits_{i=1}^{k-2}i oplus (k-1-i) + 2(0 oplus (k-1)) + 2((k-1) oplus 0))
(=2f(k-1)+4k-4)
所以：
(; ; ; ; sumlimits_{i=1}^{n-1}(ioplus (n-i)))
(=sumlimits_{i=1}^{k-1}((2i) oplus (n-2i)) + sumlimits_{i=0}^{k-1}((2i+1) oplus (n-2i-1)))
(=2f(k)+2f(k-1)+4k-4)
推导完毕。
最后用Java大数记忆化搜索。
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
public static BigInteger one = BigInteger.valueOf(1);
public static BigInteger two = BigInteger.valueOf(2);
public static BigInteger four = BigInteger.valueOf(4);
public static BigInteger six = BigInteger.valueOf(6);
public static HashMap<BigInteger, BigInteger> map = new HashMap<BigInteger, BigInteger>();
public static BigInteger F(BigInteger n) {
if(map.containsKey(n)) return map.get(n);
BigInteger k = n.divide(two);
BigInteger odd = n.mod(two);
BigInteger ans;
if(odd.compareTo(one) == 0) {
ans = F(k).multiply(four).add(k.multiply(six));
} else {
ans = F(k).multiply(two);
ans = ans.add(F(k.subtract(one)).multiply(two));
ans = ans.add(k.multiply(four)).subtract(four);
}
map.put(n, ans);
return ans;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
map.put(BigInteger.ZERO, BigInteger.ZERO);
map.put(BigInteger.ONE, BigInteger.ZERO);
while(cin.hasNext()) {
BigInteger n = cin.nextBigInteger();
System.out.println(F(n));
}
cin.close();
}
}