题解：P5177 签到

~~个人感觉还是挺简单的~~

作为一个彩笔，肯定没有大佬那么聪明的智慧，所以我先对式子进行了变形。

\sum_{i = 1}^n\sum_{j = 1}^{i - 1} i \oplus j \in [j, i]

很自然的感觉，应该对于一个

i

，后面的的

\sum_{j = 1}^{i - 1} i \oplus j \in [j, i]

应该存在一个式子可以等价。

因为是异或操作很容易想到观察二进制。

首先发现如果

i

和

j

存在相同的位数（这里指的是二进制下的）。那么无论如和

i \oplus j

的这一位都是零，肯定无法

\ge j

。所以对于

j

，位数一定小于

i

。而后我们再往下考虑下一个一，如果这一位填了一，那么之后的所有都可以随便填，假如这是第

x

位，那么贡献为

2^x

，之后也是，所以一个数的贡献是

i - 2^{high(i)}

。

2\sum_{i=1}^n\big(i-2^{high(i)}\big)

记

hp(i)=2^{high(i)}

。

2\sum_{i=1}^n\big(i- hp(i)\big) =2\Big(\sum_{i=1}^n i \;-\; \sum_{i=1}^n hp(i)\Big).

原式化为

\boxed{\,n(n+1)\;-\;2\sum_{i=1}^n hp(i)\,}.

剩下的核心问题是计算

S_{hp}(n)=\sum_{i=1}^n hp(i)

。

令

m = \lfloor \log_2 n \rfloor

，即满足

注意：在区间

[2^k,2^{k+1}-1]

上的每个整数的最高位对应的

hp(i)

都等于

2^k

。该区间包含的整数个数是

2^k

。因此，这一整段对和的贡献为

(\text{个数 }2^k)\times(\text{每个 }hp=2^k)=2^k\cdot 2^k = 4^k.

把所有完整的区间从

k=0

算到

k=m-1

，再加上最后不满的那一段（最高位为

2^m

的数）：

对于 $k=0,1,\dots,m-1$ ：贡献总和为 $\sum_{k=0}^{m-1}4^k$ 。
对于最高位为 $2^m$ 的那段：这些数是从 $2^m$ 到 $n$ ，共有 $n-2^m+1$ 个，每个的 $hp$ 都是 $2^m$ ，贡献为 $2^m\cdot (n-2^m+1)$ 。

因此

\boxed{\,\sum_{i=1}^n hp(i)=\sum_{k=0}^{m-1}4^k \;+\; 2^m\big(n-2^m+1\big)\,}.

\sum_{k=0}^{m-1}4^k=\sum_{k=0}^{m-1}4^k=\frac{4^m-1}{4-1}=\frac{4^m-1}{3}

因此

\boxed{\,\sum_{i=1}^n hp(i)=\frac{4^m-1}{3} \;+\; 2^m\big(n-2^m+1\big)\,}

文章操作