自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:12:42，当前版本为作者最后更新于2020-08-12 09:58:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

也许更好的阅读体验

---

题意：求

$$\sum_{i=1}^{2^{n}}\log_{2}{(\prod_{j=1}^{i}\operatorname{lb}(j))} $$

众所周知，看到这种输入少的题，我们应该找规律。

找个锤子规律，直接猛男推式子。

$$\begin{aligned}\sum_{i=1}^{2^{n}}\log_{2}{(\prod_{j=1}^{i}\operatorname{lb}(j))}&=\sum_{i=1}^{2^{n}}\sum_{j=1}^{i}\log_{2}{(\operatorname{lb}(j))}\\&=\sum_{j=1}^{2^{n}}\sum_{i=j}^{2^n}\log_{2}{(\operatorname{lb}(j))}\\&=\sum_{j=1}^{2^{n}}(2^n-j+1)\log_{2}{(\operatorname{lb}(j))}\\&=n+\sum_{j=1}^{2^{n}-1}(2^n-j+1)\log_{2}{(\operatorname{lb}(j))}\\&=n+\sum_{k=0}^{n-1}k\sum_{i=1}^{2^{n-k-1}}(2^n-(2i-1)2^k+1)\\&=n+\sum_{k=0}^{n-1}k(1+2^{n-1})2^{n-k-1}\\&=n+(1+2^{n-1})\sum_{k=0}^{n-1}k2^{n-k-1}\end{aligned} $$

而我们又有

$$\begin{aligned}\sum_{k=0}^{n-1}k2^{n-k-1}&=\sum_{k=1}^{n-1}k2^{n-k-1}\\&=\sum_{k=1}^{n-1}\sum_{j=1}^k2^{n-k-1}\\&=\sum_{j=1}^{n-1}\sum_{k=j}^{n-1}2^{n-k-1}\\&=\sum_{j=1}^{n-1}(2^{n-j}-1)\\&=2^n-2-(n-1)\\&=2^n-n-1\end{aligned} $$

因此

$$\sum_{i=1}^{2^{n}}\log_{2}{(\prod_{j=1}^{i}\operatorname{lb}(j))}=n+(1+2^{n-1})(2^n-n-1) $$

直接带入计算即可，使用快速幂可以 $O(\log n)$。代码就不贴了。

（题外话：$n$ 开到 $10^{10^6}$ 也没问题，快读取双模（$p,p-1$）即可）