一个关于C++的问题算法题

Question

请问各位，怎么用时间复杂度最小的方法计算出 ∏ni=1popcount(i)模10000007的值（其中popcount(i)表示i二进制表示中1的个数）

Answer 1

可以使用动态规划来计算这个式子。设 $f_i=\prod_{j=1}^{i}\text{popcount}(j)$，则 $f_n$ 是我们要计算的答案。

考虑如何利用 $f_{i-1}$ 来计算 $f_i$。对于一个数 $j$，如果 $j$ 的二进制表示中最后一位是 1，那么 $\text{popcount}(j)$ 就比 $\text{popcount}(j-1)$ 多 1；如果最后一位是 0，那么 $\text{popcount}(j)$ 就等于 $\text{popcount}(j/2)$。因此可以得到状态转移方程：

$$f_i= \begin{cases} (2f_{i-1})\bmod 10000007, & i\bmod 2=0, (f_{i-1}+\text{popcount}(i))\bmod 10000007, & i\bmod 2=1. \end{cases}$$

其中 $i\bmod 2$ 表示 $i$ 是否为偶数。

初始状态为 $f_0=1$，可以从 $f_0$ 递推得到 $f_n$。时间复杂度为 $O(n)$。