桁DPを使う.

何桁目まで見たか, 最大値かどうか, 立っているビットの数をキーとして, 数値の個数と数値の合計を値とする. これを \(C(i,j,k), S(i,j,k)\) とすると, 0 がきたときの遷移は

\[C(i+1,j^{\prime},k) += C(i,j,k) \\ S(i+1,j^{\prime},k) += 2S(i,j,k)\]

となり, 1 がきたときの遷移は

\[C(i+1,j^{\prime},k+1) += C(i,j,k) \\ S(i+1,j^{\prime},k+1) += 2S(i,j,k) + C(i,j,k)\]

となる.