\(l,r\) と \(2^{K-1}\) の大小関係で場合分けすることを考えます。

\(r \leq 2^{K-1}\) または \(l \geq 2^{K-1}\) の場合、\(K-1\) の場合と同様になります。

そうでない場合、つまり \(l < 2^{K-1} < r\) の場合は、\((l,r)=(0,2^K)\) の場合を除き、左半分 \([l,2^{K-1})\) と右半分 \([2^{K-1},r)\) に分けて、独立に考えることができます。

対称性より、以下右半分について考えます。これは、区間の左端 \(l\) を \(0\) に固定したときを考えることに対応します。\(f(0,r) = \text{popcount}(r)\) になります。よって、\(f(0,r)=k\) となる \(1 \leq r \leq 2^K\) となる \(r\) の個数を \(a_{K,k}\) とし、\(f_K(x) = \sum_{k=0}^\infty a_{K,k}x^k\) とおくと、\(f_K(x)=(1+x)^K+x-1\) となります。

さらに、\(f(l,r)=k\) となる \(0 \leq l < r \leq 2^K\) の個数を \(b_{K,k}\) とし、\(g_K(x)=\sum_{k=0}^\infty b_{K,k}x^k\) とすると、以上の考察から、以下のような漸化式が得られます:

\[ \begin{aligned} g_0(x) &=x \\ g_K(x) &= 2g_{K-1}(x)+f_{K-1}(x)^2-x^2+x \end{aligned} \]

この漸化式を式変形すると、\(g_K(x)\) は以下のようになります。

\[ \begin{aligned} g_K(x) &= f_{K-1}(x)^2+2f_{K-2}(x)^2+\dots+2^{K-1}f_0(x)^2+2^Kx+(2^K-1)(-x^2+x) \\ &= \sum_{i=0}^{K-1} 2^{K-1-i}f_i(x)^2+2^Kx+(2^K-1)(-x^2+x) \\ &= \sum_{i=0}^{K-1} 2^{K-1-i}((1+x)^i+x-1)^2+2^Kx+(2^K-1)(-x^2+x) \\ &= \sum_{i=0}^{K-1} 2^{K-1-i}(1+x)^{2i}+2(x-1)\sum_{i=0}^{K-1} 2^{K-1-i}(1+x)^i+(2^K-1)(x-1)^2+2^Kx+(2^K-1)(-x^2+x) \\ &= \sum_{i=0}^{K-1} 2^{K-1-i}(1+x)^{2i}+2(x-1)\sum_{i=0}^{K-1} 2^{K-1-i}(1+x)^i+x+2^N-1 \end{aligned} \]

よって、\(\sum_{i=0}^{K-1} 2^{K-1-i}(1+x)^{2i}\) と \(\sum_{i=0}^{K-1} 2^{K-1-i}(1+x)^i\) を計算することに帰着します。

等比数列の和の公式により、\(\sum_{i=0}^{K-1} 2^{K-1-i}(1+x)^{2i}=\frac{2^K-(1+x)^{2K}}{1-2x-x^2}, \sum_{i=0}^{K-1} 2^{K-1-i}(1+x)^i=\frac{2^K-(1+x)^K}{1-x}\) となるので、二項係数の前計算と疎な多項式による除算を用いて \(\mathrm{O}(K)\) 時間で求めることができます。