推式子专区

① 给定正整数 $n$，求：

$$\sum_{i=1}^{2^n}\log_2(\prod_{j=1}^{i}lowbit(j))$$

其中 $lowbit(x)$ 即 $x$ 与 $-x$ 按位与的结果。

子任务：

　　$\text{Subtack 1 : } n \le 20.$

　　$\text{Subtack 2 : } n \le 60.$

　　$\text{Subtack 3 : } n \le 10^5.$

　　$\text{Subtack 4 : } n \le 2^{62}.$

过程：

$$\sum_{i=1}^{2^n}\log_2(\prod_{j=1}^{i}lowbit(j))$$
$$=\sum_{i=1}^{2^n}\sum_{j=1}^{i}\log_2(lowbit(i))$$

　　通过递推，可以通过 $\text{Subtack 1}$；

　　继续观察，可以发现 $\log_2(lowbit(x))$ 就是 $x$ 分解质因子后质因子 $2$ 的指数。

　　所以，可以化成

$$=\sum^{2^n}_{i=1}\sum^{\log_2i}_{j=1}\lfloor \frac{i}{2^j}\rfloor$$

$$=\sum^{2^n}_{i=1}\sum^{\log_2{2^n}}_{j=1}\lfloor \frac{i}{2^j}\rfloor$$

$$=\sum^{n}_{i=1}\sum_{j=1}^{2^n}\lfloor \frac{j}{2^i}\rfloor$$

　　然后，尝试发现一些性质：

　　将 $0,1,...,2^i-1$ 分成一组，$2^i,2^i+1,...,2^{i+1}-1$ 分成一组，……，最后将 $2^n$ 单独放一组，这样每一组有 $2^i$ 个数字。

　　根据下取整函数，可以得到

$$=\sum_{i=1}^n\sum_{j=0}^{2^{n-i}-1}j \cdot 2^i+\sum_{i=1}^{n}2^{i-1}$$
$$=\sum_{i=1}^n 2^i\sum_{j=0}^{2^{n-i}-1}j+\sum_{i=1}^{n}2^{i-1}$$

　　利用等差数列求和公式，变成

$$=\sum_{i=1}^n 2^i \cdot\frac{(2^{n-i}-1) \cdot (2^{n-i})}{2}+\sum_{i=1}^{n}2^{i-1}$$
$$=\sum_{i=1}^n 2^{i-1} \cdot(2^{n-i}-1) \cdot 2^{n-i}+\sum_{i=1}^{n}2^{i-1}$$

　　到此处可以通过 $\text{Subtack 2 和 3}$；

　　我们发现，中间 $2^{n-i}-1$ 的那个 $1$ 可以分开算，所以分离得

$$=\sum_{i=1}^n 2^{i-1} \cdot 2^{n-i} \cdot 2^{n-i}-\sum_{i=1}^{n}2^{i-1}\cdot2^{n-i}+\sum_{i=1}^{n}2^{i-1}$$
$$=\sum_{i=1}^n 2^{2n-i-1}-\sum_{i=1}^{n}2^{n-1}+\sum_{i=1}^{n}2^{i-1}$$
$$=\sum_{i=1}^n 2^{2n-i-1}-n \cdot2^{n-1}+\sum_{i=1}^{n}2^{i-1}$$
$$=\sum_{i=n-1}^{2n-2} 2^{i}-n \cdot2^{n-1}+\sum_{i=1}^{n}2^{i-1}$$

　　发现其中几部分是等比数列，直接套用公式得

$$=2\cdot2^{2n-2}-2^{n-1}-n \cdot2^{n-1}+2^n-1$$
$$=2^{2n-1}-(n+1) \cdot2^{n-1}+2^n-1$$

　　此时复杂度是 $\log$ 级别的（快速幂），可以通过 $\text{Subtack 4}$。

推式子专区

原文：https://www.cnblogs.com/zengpeichen/p/11821882.html