专栏文章

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

CCleverSea
P12147题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miox7787
此快照首次捕获于
2025/12/03 02:37
3 个月前
此快照最后确认于
2025/12/03 02:37
3 个月前
查看原文

在前言前面

很遗憾，您的题解不符合推荐标准。原因是：非数学公式（一般英文单词、题目名、算法名、人名等）不应使用 LaTeX。
可我寻思着题面就是这么写的啊……

前言（读后续写）

ほら、星屑がそっと揺れるよ\text{ほら、星屑がそっと揺れるよ}
明日の風が頬を撫でる\text{明日の風が頬を撫でる}
その小さな傘、差していこう\text{その小さな傘、差していこう}
君の物語は続いて征く\text{君の物語は続いて征く}
这里是翻译（剪贴板）。（机翻没有美感）

题意简述

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

分析

注意到，函数 f(x)=x⊕(x+2k)f(x) = x \oplus (x + 2^k) 的取值取决于 xx 的第 kk 位：
  • 如果 xx 的第 kk 位为 00，则 f(x)=2kf(x) = 2^k。
  • 如果 xx 的第 kk 位为 11，则 f(x)f(x) 的取值不仅包括第 kk 位，还可能包括从第 kk 位开始向上连续的一段 11（由进位引起）。
为了高效计算 SS，我们按位贡献考虑：
  1. 第 kk 位：每个 xx 的第 kk 位在 f(x)f(x) 中总是 11，因此贡献为 (n+1)×2k(n+1) \times 2^k。
  2. 第 ii 位（i>ki > k）：当且仅当 xx 的第 kk 位到第 i−1i-1 位全为 11 时，f(x)f(x) 的第 ii 位为 11。设满足条件的 xx 的个数为 g(i,k,n)g(i, k, n)，则第 ii 位的贡献为 g(i,k,n)×2ig(i, k, n) \times 2^i。
So，总和 SS 为：
S=(n+1)×2k+∑i=k+1max_bitg(i,k,n)×2iS = (n+1) \times 2^k + \sum_{i=k+1}^{\text{max\_bit}} g(i, k, n) \times 2^i
其中 max_bit\text{max\_bit} 取足够大的值（如 6060），因为 n<229n < 2^{29}，更高位无贡献。
所以我们只需要考虑如何计算 g(i,k,n)g(i, k, n)。不妨设 L=kL = k，R=i−1R = i-1，则要求 xx 的二进制表示中 [L,R][L, R] 位全为 11。构造 M=(2R+1−1)−(2L−1)=2R+1−2LM = (2^{R+1} - 1) - (2^L - 1) = 2^{R+1} - 2^L（即 [L,R][L, R] 位全 11 的数）。若 M>nM > n，则 g(i,k,n)=0g(i, k, n) = 0。否则，令 T=n−MT = n - M，W=2R+1W = 2^{R+1}，X=2L−1X = 2^L - 1（低位最大值）。计算满足 0≤A≤⌊TW⌋0 \leq A \leq \lfloor \frac{T}{W} \rfloor 的整数 AA 的数量，使得 B=T−A×W≤XB = T - A \times W \leq X 或 B≥0B \geq 0。
然后分讨一下——对于 g(i,k,n)g(i, k, n)，可以分为两部分：
  1. AA 较小，BB 可取 [0,X][0, X]：方案数为 (min⁡(A0,Amax⁡)+1)×2L(\min(A_0, A_{\max}) + 1) \times 2^L，其中 A0=⌊T−XW⌋A_0 = \lfloor \frac{T - X}{W} \rfloor，Amax⁡=⌊TW⌋A_{\max} = \lfloor \frac{T}{W} \rfloor。
  2. AA 较大，BB 可取 [0,T−A×W][0, T - A \times W]：方案数为 ∑A=A0+1Amax⁡(T−A×W+1)\sum_{A=A_0+1}^{A_{\max}} (T - A \times W + 1)，可用小奥学的等差数列求和公式计算。

CodeCode

CPP
#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)O(kT)，其中 k=60k = 60。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...