题解：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 的数）：

因此

\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)\,}