P5627 【AFOI-19】sum与prod

· · 题解

我再也不开数学题了。

Statement

给定 n，求

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

Solution

显然地，由于 \log 的性质 \log_kNM=\log_kN+\log_kM，所以原式等价于

\sum_{i=1}^{2^n}\sum_{j = 1}^i\log_2\left(lowbit(j) \right)

这玩意是一个前缀和的前缀和，对于极大的 n 肯定是难维护的。

考虑转换思路，我们先来看看 \log_2(lowbit(i)) 这个序列长啥样。

0 1 0 2 0 1 0 3 0 1 0 2 0 1 4 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 5 ......

发现我们的答案就是对这个序列的前缀和做前缀和。考虑一种 \log_2(lowbit(i)) = k，k 会对这个答案有多少贡献。

假定 n = 3,k = 0，此时我们只看前面这一段：

0 1 0 2 0 1 0 3

我们发现，有 4 个 0，他们的贡献是对后面一整段产生的，分别是 8 \cdot 0，6 \cdot 0，4 \cdot 0 和 2 \cdot 0。我们不关心后面乘上的这个权 0，只关心前面的这一部分 8，6，4 和 2。显然是个等差数列。求和就十分简单，我们发现第一项其实是 2^n-2^k+1，最后一项是 2^k+1，项数是 2^{n-k-1}，所以总的贡献是：

\dfrac{ \left( 2^n-2^k+1+2^k+1 \right)}{2} \cdot 2^{n - k - 1} \cdot k

整理得

\left( 2^{n - 1} + 1 \right) \cdot 2^{n - k - 1} \cdot k

然后我们注意到 k \le n。不难发现当 k = n 时这个式子是错误的，原因是 k=n 时正好是最后一个，贡献是 n \cdot 1，那就干脆把这个单独拿出来，所以原式等价于：

n + \sum_{k = 1}^{n - 1}\left( 2^{n - 1} + 1 \right)\cdot 2^{n - k - 1} \cdot k

将与 k 无关的部分提出来得到

n + \left( 2^{n - 1} + 1 \right) \cdot 2 ^ n \cdot \sum_{k = 1}^{n - 1} \dfrac{k}{2^{k + 1}}

得到最终式子

n + \left( 2^{2n - 1} + 2^n \right)\sum_{k = 1}^{n - 1} \dfrac{k}{2^{k + 1}}

复杂度 \Theta\left(n\log n\right)，可以拿到 50 分。

考虑如何化简后面这个求和，记

S=\sum_{k = 1}^{n - 1} \dfrac{k}{2^{k + 1}}

则

\dfrac{1}{2}S=\sum_{k = 1}^{n - 1} \dfrac{k}{2^{k + 2}} S - \dfrac{1}{2}S=\sum_{k = 1}^{n - 1} \dfrac{1}{2^{k + 1}} - \dfrac{n - 1}{2^{n + 1}} \dfrac{1}{2}S=\dfrac{1}{2}-\dfrac{1}{2^n} -\dfrac{n - 1}{2^{n + 1}} S=\dfrac{2^{n} - n - 1}{2^n}

大功告成。代入得原式等于

n + \left( 2^{2n - 1} + 2^n \right)S

即

n + (2 ^ {n - 1} + 1)(2^n - n - 1)

发现这个式子的瓶颈在于计算 2 的幂次，快速幂做完了，复杂度 \Theta\left(\log n\right)，可以通过本题。

Details

注意取模，记得要对所有不在指数上的 n 取模，否则会挂。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n;
int ans;
constexpr int mod = 1e9 + 7;
int qpow(int x, int a) {
    int res = 1;
    while (a) {
        if(a & 1) res = res * x % mod;
        x = x * x % mod;
        a >>= 1;
    }
    return res % mod;
}
signed main(void) {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    ans = qpow(2, n - 1) + 1;
    ans %= mod;
    ans = ans * (qpow(2, n) - n % mod + mod - 1 + mod + mod) % mod;
    ans = (ans + n) % mod;
    cout << ans;
    return 0;
}