【思路分析】

数位 DP（Digit DP）+ Popcount 限制

问题本质：

我们需要枚举 x 的所有可能值$（1≤x≤N）$中，二进制中恰好有 K 个 1 的数的和。 直接枚举会超时，因为 N 最多可达 $2^{60}$ 级别。因此我们使用 数位动态规划（Digit DP） 的思想。

📐 状态设计

用 $f[pos][cnt][tight]$ 和 $g[pos][cnt][tight]$ 表示： • $f[pos][cnt][tight]$：表示从第 $pos$ 位开始，已经选了 $cnt$ 个 1，当前是否处于 “紧贴 $N$ 的前缀”（$tight=1$） 的情况下，有多少种合法数字组合。 • $g[pos][cnt][tight]$：在上述状态下，这些合法数字组合的数字之和。

💡 状态转移过程说明（从高位向低位转移）：

• 假设当前处理的是第 $i$ 位（从高位向低位），可以选择这一位为 $0$ 或 $1$； • 要维持不超过 $N$，所以需要一个 $tight$ 标志； • 如果 $n$的第位是$1$，可以选择当前位为0（$tight$从1→0），或者保持为1； • 如果 $n$ 的第 $i$ 位是 0，只能选 0， $tight$继续维持为 1； • 每次选 1 时， $cnt$也需要加 1，并且加上当前位代表的数值 $2^i$ 到 $g$ 中。

示例（简化说明）

假设 $N=10=1010_2$，，我们想找所有 $≤10$ 的数中，二进制中正好有 2 个 1 的所有数的和。 合法数有：$3(11)、5(101)、6(110)、9(1001)、10(1010)$ 这些数的和是：$3+5+6+9+10=33$

f[61][0][1] = 1;

初始状态：从最高位 60 开始，选了 0 个 1，处于 $tight$ 状态。

for (int i = 60; i >= 0; i--) {
    int d = (1ll << i), dm = d % Mod;

从高位往低位遍历， d是当前位的值，后续加和要乘以该值。

if (n & d) { ... } else { ... }

根据 n 当前位是 1 还是 0，确定 $tight$ 转移方式。 每次转移： • 更新 f 计数（有多少种方案）； • 更新 g 和值（这些方案的总和）； • 注意 $modular$ 加法。