可以使用动态规划来计算这个式子。设 $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)$。因此可以得到状态转移方程:
fi={(2fi−1)mod
其中 $i\bmod 2$ 表示 $i$ 是否为偶数。
初始状态为 $f_0=1$,可以从 $f_0$ 递推得到 $f_n$。时间复杂度为 $O(n)$。