版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [Luogu P5627] 【AFOI-19】sum与prod" categories:
SY 终于整理好了她凌乱的被子, 刚来到教室的她就收到了 QM 传来的一张字条.
To: Dear SY
$~~~~$ 你看看我昨晚梦到的式子, 解出来给你糖吃
From: Your QM
SY 自然是无法拒绝 $C{6}H{12}O_{6}$ 的诱惑啦, 不过她看到字条背面花里胡哨的式子时傻眼了. . 但是 SY 还是很想吃糖
求
$$ \sum{i=1}^{2^{n}}\log{2}{(\prod_{j = 1}^{i}lowbit(j))} $$
的结果
其中 $lowbit(x)$ 意指x&(~x+1)的结果
一行, 一个整数 n
一行, 一个整数, 为答案模 $10^9+7$ 的结果
2
5
5
447
对于前 $20\%$ 的数据, 有 $\leq n \leq 60$
对于前 $50\%$ 的数据, 有 $\leq n \leq 10^4$
对于前 $100\%$ 的数据, 有 $\leq n \leq 2^{62}$
容易得到, 原式即为
$$ \begin{aligned} &+0\ &+0+1\ &+0+1+2\ &+0+1+2+2\ &...\ &+0+1+2+2+...+\underbrace{k+k+...+k}_{k}+...+\underbrace n_1\ \end{aligned} $$
即 $n+(1+2^{n-1})(2^n-n-1)$