题解 P5627 【【AFOI-19】sum与prod】

· · 题解

也许更好的阅读体验

题意：求

\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）即可）