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$。

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

设 $f(n) = \sum_{i=0}^{n} (i \oplus n-i)$。

如果 $n$ 为偶数。

重要观察：$i$ 与 $n-i$ 的奇偶性相同，因此：

$$\begin{align*} f(n) &= \sum_{i=0}^{n} (i \oplus n-i) \\ &= 2 \times\sum_{i=0}^{n} (\lfloor \frac{i}{2} \rfloor \oplus \lfloor \frac{n-i}{2} \rfloor) \end{align*}$$

向下取整对于奇偶和偶数的运算是不同的，因此将 $i$ 为奇数和偶数的情况分开：

$$\begin{align*} f(n) &= \sum_{i=0，为偶数}^{n} (i \oplus n-i) + \sum_{i=0，为奇数}^{n} (i \oplus n-i) \\ &= 2 \times\sum_{i=0，为偶数}^{n} (\frac{i}{2} \oplus \frac{n-i}{2}) + 2 \times\sum_{i=0，为奇数}^{n} (\frac{i-1}{2} \oplus \frac{n-i-1}{2}) \\ &= 2 \times\sum_{i=0}^{\frac{n}{2}} (i \oplus \frac{n}{2} - i) + 2 \times\sum_{i=0}^{\frac{n}{2}-1} (i \oplus \frac{n}{2}-1 -i) \\ &= 2f(\frac{n}{2}) + 2f(\frac{n}{2}-1) \end{align*}$$

如果 $n$ 为奇数。

重要观察：$i$ 与 $n-i$ 的奇偶性不同，因此：

$$\begin{align*} f(n) &= \sum_{i=0}^{n} (i \oplus n-i) \\ &= \sum_{i=0}^{n} [ 2 \times (\lfloor \frac{i}{2} \rfloor \oplus \lfloor \frac{n-i}{2} \rfloor) + 1 ] \end{align*}$$

依然对于 $i$ 奇偶分类：

$$\begin{align*} f(n) &= 2 \times \sum_{i=0}^{n} (\lfloor \frac{i}{2} \rfloor \oplus \lfloor \frac{n-i}{2} \rfloor) + n + 1 \\ &= 2 \times [\sum_{i=0,为奇数}^{n}(\frac{i-1}{2} \oplus \frac{n-i}{2}) + \sum_{i=0,为偶数}^{n}(\frac{i}{2} \oplus \frac{n-i-1}{2})] + n + 1 \end{align*}$$

中括号内两坨东西是对称、等价的。

$$\begin{align*} f(n) &= 2 \times 2 \times \sum_{i=0}^{\frac{n-1}{2}}(i \oplus \frac{n-i}{2} - i) + n + 1\\ &= 4 \times f(\frac{n-1}{2}) + n + 1\\ \end{align*}$$

初始化 $f(0) = 0$。
上述的递推可以使用记忆化递归实现。
需要写一个高精度。

但是，你要注意了，$ans = \sum_{i=1}^{n-1} (i \oplus n-i) = f(n) - 2n$。

代码实现

这是我熬到 12 点写出的高精度，希望大家喜欢。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef vector<int> BigInt;
map<BigInt, BigInt> f;

BigInt read(){
	string s;
	cin >> s;
	int len = (int)s.size();
	BigInt res(len, 0);
	for(int i = 0; i < len; i ++) res[len - i - 1] = s[i] - '0';
	return res;
}

void write(BigInt x){
	for(int i = (int)x.size()-1; i >= 0; i --){
		cout << x[i];
	}
}

BigInt tran(int x){
	if(x == 0) return BigInt(1, 0);
	BigInt res;
	while(x > 0){
		res.push_back(x%10);
		x/=10;
	}
	return res;
}

//加法

BigInt operator + (const BigInt &a, const BigInt &b){
	BigInt x = a, y = b;
	int len = (int)max(x.size(), y.size()) + 1;
	BigInt res(len, 0);
	x.resize(len), y.resize(len);
	for(int i = 0; i < (int)res.size() - 1; i ++){
		res[i] += x[i] + y[i];
		res[i+1] += res[i] / 10;
		res[i] %= 10;
	}
	while(res.back() == 0 && res.size() > 1){
		res.pop_back();
	}
	len = (int)res.size();
	while(res[len - 1] >= 10){
		res.push_back(res[len-1]/10);
		res[len-1] %= 10;
		len++;
	}
	return res;
}

BigInt operator + (const BigInt &x, const int &y){ return x + tran(y); }
BigInt operator + (const int &x, const BigInt &y){ return tran(x) + y; }


//减法
//默认 x >= y
BigInt operator - (const BigInt &a, const BigInt &b){
	int len = (int)max(a.size(), b.size())+1;
	BigInt res = a, y = b;
	res.resize(len), y.resize(len);
	for(int i = 0; i < len-1; i ++){
		if(res[i] < y[i]){
			res[i+1]--;
			res[i]+=10;
		}
		res[i] -= y[i];
	}
	while(res.size() > 1 && res.back() == 0){
		res.pop_back();
	}
	return res;
}


BigInt operator - (const BigInt &x, const int &y){ return x - tran(y); }
BigInt operator - (const int &x, const BigInt &y){ return tran(x) - y; }

//乘法
BigInt operator * (const BigInt &x, const BigInt &y){
	int len = (int)x.size() + (int)y.size();
	BigInt res(len, 0);
	for(int i = 0; i < (int)x.size(); i ++){
		for(int j = 0; j < (int)y.size(); j ++){
			res[i+j] += x[i] * y[j];
		}
	}
	while(res.size() > 1 && res.back() == 0){
		res.pop_back();
	}
	for(int i = 0; i < (int)res.size() - 1; i ++){
		res[i+1] += res[i]/10;
		res[i]%=10;
	}
	while(res[res.size()-1]>=10){
		len = (int)res.size();
		res.push_back(res[len-1]/10);
		res[len-1]%=10;
	}
	return res;
}

BigInt operator * (const BigInt &x, const int &y){ return x * tran(y); }
BigInt operator * (const int &x, const BigInt &y){ return tran(x) * y; }

//除法, 保证可以整除,且x > y
BigInt operator / (const BigInt &x, const int &y){
	BigInt res(x.size(), 0);
	int now = 0;
	for(int i = (int)x.size()-1; i >= 0; i --){
		now = 10*now + x[i];
		if(now >= y){
			res[i] = now/y;
			now%=y;
		}
	}
	while(res.back() == 0 && res.size() > 1){
		res.pop_back();
	}
	return res;
}

BigInt dfs(BigInt x){
	if(f.count(x)) return f[x];
	else if(x[0] % 2 == 1){
		return f[x] = 4 * dfs((x - 1) / 2) + x + 1;
	}else{
		
		return f[x] = 2 * dfs(x/2) + 2 * dfs(x/2-1);
	}
}

int main(){
	f[tran(0)] = BigInt(tran(0));
	BigInt n = read();
	write(dfs(n) - 2*n);
	return 0;
}

ROX

不难想到找规律，旁边的 DP。

666，这题是找规律我直接 AFO。找规律不是找关于通项公式的吗？我这个函数是递推的，我找什么？？？？瞪出递推公式吗？？？？

显然，你用线性的复杂度打出表，发现没有任何的规律。至少你瞪不出来（菜就多练）。

所以，这种神秘题目应当考虑 DP.

观察可得，我们给他二进制拆分一波，发现每一位似乎是独立的。

于是，我们从高向低地推。

令现在考虑的数字为 $k$。

$(k)_2 = (\cdots 0)$，如果原数字二进制表示是左边形式，也就是偶数，不难发现 $2^0$ 不做贡献，答案就是 $2f(k/2)+2f(k/2-1)$，因为右移一位后，答案要乘 $2$， $k/2$ 对应另一个数是偶数，反过来就是奇数。

反之，$(k)_2 = (\dots 1)$，如果原数字是奇数，无论另一个数字的取值，都有 $2^0$ 的贡献。一共有 $2 \times (k / 2 + 1)$ 个，另一个数出去末位，他的取值是 $k/2 + 1$ （有 $0$），再乘上 $2$，因为末位可 $1$ 可 $0$。然而，前面的数位还有 $4f(k/2)$ 的贡献。因为先乘 $2$ ，保证位数对齐。再乘 $2$ 因为末位可 $1$ 可 $0$。

具体的方程直接看 WZH 的。

最后 DP 即可，有高精度。