题解：P12147 【MX-X11-T1】「蓬莱人形 Round 1」仅此而已，就已经足够了

· · 题解

在前言前面

很遗憾，您的题解不符合推荐标准。原因是：非数学公式（一般英文单词、题目名、算法名、人名等）不应使用 LaTeX。

可我寻思着题面就是这么写的啊……

前言（读后续写）

\text{ほら、星屑がそっと揺れるよ} \text{明日の風が頬を撫でる} \text{その小さな傘、差していこう} \text{君の物語は続いて征く}

这里是翻译（剪贴板）。（机翻没有美感）

题意简述

定义函数 f(x) = x \oplus (x + 2^k)，给定两个整数 n 和 k，计算 S = \sum_{x=0}^{n} f(x) 的值。

分析

注意到，函数 f(x) = x \oplus (x + 2^k) 的取值取决于 x 的第 k 位：

为了高效计算 S，我们按位贡献考虑：

  1. 第 k 位：每个 x 的第 k 位在 f(x) 中总是 1，因此贡献为 (n+1) \times 2^k。

  2. 第 i 位（i > k）：当且仅当 x 的第 k 位到第 i-1 位全为 1 时，f(x) 的第 i 位为 1。设满足条件的 x 的个数为 g(i, k, n)，则第 i 位的贡献为 g(i, k, n) \times 2^i。

So，总和 S 为：

S = (n+1) \times 2^k + \sum_{i=k+1}^{\text{max\_bit}} g(i, k, n) \times 2^i

其中 \text{max\_bit} 取足够大的值（如 60），因为 n < 2^{29}，更高位无贡献。

所以我们只需要考虑如何计算 g(i, k, n)。不妨设 L = k，R = i-1，则要求 x 的二进制表示中 [L, R] 位全为 1。构造 M = (2^{R+1} - 1) - (2^L - 1) = 2^{R+1} - 2^L（即 [L, R] 位全 1 的数）。若 M > n，则 g(i, k, n) = 0。否则，令 T = n - M，W = 2^{R+1}，X = 2^L - 1（低位最大值）。计算满足 0 \leq A \leq \lfloor \frac{T}{W} \rfloor 的整数 A 的数量，使得 B = T - A \times W \leq X 或 B \geq 0。

然后分讨一下——对于 g(i, k, n)，可以分为两部分：

Code

#include <bits/stdc++.h>
#define Code using
#define by namespace
#define CleverSea std
typedef long long ll;

Code by CleverSea;

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll n, k;
        cin >> n >> k;
        // 第 k 位的贡献：每个 x 都有贡献
        ll ans = (n + 1) * (1LL << k);
        // 枚举更高位 i (i > k)
        for (int i = k + 1; i <= 60; i++) {
            int L = k;          // 区间起点
            int R = i - 1;      // 区间终点
            // 计算 M = 2^{R+1} - 2^L，即 [L, R] 位全 1 的数
            ll M_val = (1LL << (R + 1)) - (1LL << L);
            if (M_val > n) continue;  // 无满足条件的 x
            ll T_val = n - M_val;     // 剩余值
            ll W_val = (1LL << (R + 1)); // 模数 W = 2^{R+1}
            ll A_max = T_val / W_val; // A 的最大值
            ll X_val = (1LL << L) - 1; // 低位最大值 (2^L - 1)
            // 计算 A0：满足 T_val - A*W_val >= X_val 的最大 A
            ll A0;
            if (T_val < X_val) {
                A0 = -1;
            } else {
                A0 = (T_val - X_val) / W_val;
            }
            // 第一部分：A 从 0 到 min(A0, A_max)，每个 A 贡献 2^L 个 B
            ll part1 = 0;
            ll A1 = min(A0, A_max);
            if (A1 >= 0) {
                part1 = (A1 + 1) * (1LL << L);
            }
            // 第二部分：A 从 A0+1 到 A_max，每个 A 贡献 (T_val - A*W_val + 1) 个 B
            ll part2 = 0;
            ll A_start = A1 + 1;
            ll A_end = A_max;
            if (A_start <= A_end) {
                ll cnt = A_end - A_start + 1; // A 的个数
                // 等差数列求和：Σ_{A=A_start}^{A_end} (T_val - A*W_val + 1)
                part2 = (T_val + 1) * cnt - W_val * (A_start + A_end) * cnt / 2;
            }
            ll g = part1 + part2; // 满足条件的 x 的数量
            ans += g * (1LL << i); // 第 i 位的贡献
        }
        cout << ans << '\n';
    }
    return 0;
}

时间复杂度为 O(kT)，其中 k = 60。