题解：花神的数论题

核心问题

求： [ \prod_{i=1}^N \text{sum}(i) \ (\text{mod } 10^7+7) ] 其中 $\text{sum}(i)$ 是 $i$ 的二进制表示中 $1$ 的个数。

数据范围

$N \le 10^{15}$，无法枚举，需用 数位 DP。

解题思路

将问题转化为：
对于每个可能的 $1$ 的个数 $k$，计算在 $[1,N]$ 中有多少个数其二进制恰有 $k$ 个 $1$，记为 $cnt[k]$。
则答案为： [ \prod_{k=1}^{\text{max_bits}} k^{cnt[k]} \ (\text{mod } 10^7+7) ]

数位 DP 设计：

• 状态：dfs(pos, limit, sum)
  • pos：当前处理到二进制第几位（从高位到低位）
  • limit：是否受到 $N$ 的限制
  • sum：当前已选的 $1$ 的数量
• 返回值：从当前状态开始，后续所有数对应的 $\text{sum}(i)$ 乘积

转移时，当前位可选 $0$ 或 $1$（受限制时不能超过 $N$ 的对应位），递归计算子问题乘积，乘起来即可。

代码要点

• 将 $N$ 转为二进制数组 a[]
• 用记忆化 f[pos][sum] 加速（当 limit=0 时）
• 递归边界：pos=0 时返回 max(sum,1)（因为 $\text{sum}(i) \ge 1$）
• 所有乘法取模 $10^7+7$

时间复杂度

状态数 $O(\log N \times \log N)$，可高效处理 $N=10^{15}$。