题意：
定义
\]
求\(f(n),n \leq 10^{500}\)
分析：
这个数列对应OEIS的A006582
先上公式：
4f(k)+6k,n=2k+1\\
2f(k)+2f(k-1)+4k-4,n=2k
\end{matrix}\right.\]
递推的思路就是虽然不知道两个数的异或值，但是如果知道这两个数的奇偶性那么结果的奇偶性也就知道了。
还有一个公式：\(2a \oplus 2b = 2(a \oplus b)\)，这个也很容易理解。
下面开始证明：
- \(n=2k+1\)时：
\(\; \; \; \; \sum\limits_{i=1}^{n-1}(i\oplus (n-i))\)
\(=2\sum\limits_{i=1}^{k}((2i) \oplus (n-2i))\)
\(=2\sum\limits_{i=1}^{k}((2i) \oplus (2k-2i+1))\)
\(=2\sum\limits_{i=1}^{k}((2i) \oplus (2k-2i) + 1)\)
\(=2\sum\limits_{i=1}^{k}((2i) \oplus (2k-2i)) + 2k\)
\(=4\sum\limits_{i=1}^{k}((i) \oplus (k-i)) + 2k\)
\(=4\sum\limits_{i=1}^{k-1}((i) \oplus (k-i)) + 4(k \oplus (k-k)) + 2k\)
\(=4f(k)+6k\)
- \(n-2k\)时：
\(\; \; \; \; \sum\limits_{i=1}^{n-1}(i\oplus (n-i))\)
\(=\sum\limits_{i=1}^{k-1}((2i) \oplus (n-2i)) + \sum\limits_{i=0}^{k-1}((2i+1) \oplus (n-2i-1))\)
\(\; \; \; \; \sum\limits_{i=1}^{k-1}((2i) \oplus (n-2i))\)
\(=\sum\limits_{i=1}^{k-1}((2i) \oplus (2k-2i))\)
\(=2\sum\limits_{i=1}^{k-1}(i \oplus (k-i))\)
\(=2f(k)\)
\(\; \; \; \; \sum\limits_{i=0}^{k-1}((2i+1) \oplus (n-2i-1))\)
\(=\sum\limits_{i=0}^{k-1}((2i) \oplus (2k-2i-2))\)，两边都是奇数，把末位的\(1\)去掉后异或值不变
\(=2\sum\limits_{i=0}^{k-1}i \oplus (k-1-i)\)
\(=2\sum\limits_{i=1}^{k-2}i \oplus (k-1-i) + 2(0 \oplus (k-1)) + 2((k-1) \oplus 0)\)
\(=2f(k-1)+4k-4\)
所以：
\(\; \; \; \; \sum\limits_{i=1}^{n-1}(i\oplus (n-i))\)
\(=\sum\limits_{i=1}^{k-1}((2i) \oplus (n-2i)) + \sum\limits_{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();
}
}