• \(c(n, k)\) を、\(0\) 以上 \(n\) 以下の整数のうち popcount が \(k\) であるものの個数
• \(s(n, k)\) を、\(0\) 以上 \(n\) 以下の整数のうち popcount が \(k\) であるものの総和

と定めます。つまり

\(\begin{aligned} c(n, k) &= \sum_{\substack{0 \leq x \leq n \\ \mathrm{popcount}(x) = k}} 1, \\ s(n, k) &= \sum_{\substack{0 \leq x \leq n \\ \mathrm{popcount}(x) = k}} x \end{aligned}\)

です。答えは \(s(N, K)\) です（\(x = 0\) を含めても問題ありません）。

\(x\) の最も下の桁が \(0\) か \(1\) かで場合分けすることにより、

\(\begin{aligned} c(n, k) &= \sum_{\substack{0 \leq 2y \leq n \\ \mathrm{popcount}(2y) = k}} 1 + \sum_{\substack{0 \leq 2y+1 \leq n \\ \mathrm{popcount}(2y+1) = k}} 1 \\ &= \sum_{\substack{0 \leq y \leq \left\lfloor \frac{n}{2}\right\rfloor \\ \mathrm{popcount}(y) = k}} 1 + \sum_{\substack{0 \leq y \leq \left\lfloor \frac{n-1}{2}\right\rfloor \\ \mathrm{popcount}(y) = k-1}} 1 \\ &= c\left(\left\lfloor \frac{n}{2} \right\rfloor,k \right) + c\left(\left\lfloor \frac{n-1}{2} \right\rfloor,k-1 \right) , \\ s(n, k) &= \sum_{\substack{0 \leq 2y \leq n \\ \mathrm{popcount}(2y) = k}} 2y + \sum_{\substack{0 \leq 2y+1 \leq n \\ \mathrm{popcount}(2y+1) = k}} (2y+1) \\ &= \sum_{\substack{0 \leq y \leq \left\lfloor \frac{n}{2}\right\rfloor \\ \mathrm{popcount}(y) = k}} 2y + \sum_{\substack{0 \leq y \leq \left\lfloor \frac{n-1}{2}\right\rfloor \\ \mathrm{popcount}(y) = k-1}} (2y+1) \\ &= 2s\left(\left\lfloor \frac{n}{2} \right\rfloor,k\right) + 2s\left(\left\lfloor \frac{n-1}{2} \right\rfloor,k-1 \right) + c\left(\left\lfloor \frac{n-1}{2} \right\rfloor,k-1 \right) \end{aligned}\)

です。

これをメモ化再帰で実装することで解くことができます。再帰関数が呼び出される回数は \(1\) ケースあたり \(O(\log^2 N)\) です。