この問題は，桁DPを行うことで解くことができます．

本問のように，「\(N\) 以下の値に対して何かの値を求める」という類の問題に対しては，桁DPが適用できることが多いです．その場合，上の桁から順に見て行き，\(N\) より小さい値であることが確定している場合の値としていない値の場合に分けて値を保持しておくことで遷移を行う，という定石が取られることが多いです．

本問についても例外ではなく，この方法を採ることができますので，以下ではその方法について解説していきます．

（※なお，桁DPには下の桁から見て遷移を行い，再帰的に問題を解いていく方法（俗に竹DPとも呼ばれます：「けた」の逆さ読みで「たけ」となっているのだと推測されます）もあります．その方法は miscalculation53さんの解説にありますのでそちらを参照してください．）

以下の \(2\) つの量を持ちます．なお，解説の都合上，ビット長は \(L = 60\) であるものとします．

• \(dp_1(i, j)\)：\(i\) ビット目までを埋めた時点で \(N\) より小さいことが確定している非負整数であって，立っているビットが上から \(i\) ビット目までであり，立っているビット数が \(j\) であるものの個数
• \(dp_2(i, j)\)：\(i\) ビット目までを埋めた時点で \(N\) より小さいことが確定している非負整数であって，立っているビットが上から \(i\) ビット目までであり，立っているビット数が \(j\) であるものの総和

はじめ，dp テーブルの値は全て \(0\) で初期化されています．

この DP の遷移を考えます．すなわち，上のビットから順に，そのビットを立てるか立てないかを選択していきます．

まず，\(dp_1(*, *)\) および \(dp_2(*, *)\) 同士の遷移を考えます．このテーブルでは \(N\) より小さい値のみを考慮しているため，ビットを立てるか立てないかの選択を自由に行えます．

したがって，ビットを立てる選択をした場合は

• \(dp_1(i, j) \leftarrow dp_1(i, j) + dp_1(i - 1, j - 1)\)
• \(dp_2(i, j) \leftarrow dp_2(i, j) + dp_2(i - 1, j - 1) + dp_1(i - 1, j - 1) \times 2^{L-i}\)

ビットを立てない選択をした場合は

• \(dp_1(i, j) \leftarrow dp_1(i, j) + dp_1(i - 1, j)\)
• \(dp_2(i, j) \leftarrow dp_2(i, j) + dp_2(i - 1, j)\)

のように遷移できます．

また，\(N\) の \(i\) ビット目が立っている場合は，\(N\) から \(dp_1(i, j), dp_2(i, j)\) への遷移も別で行います．事前にここまでで立っているビットの数 \(b\) およびここまでで見たビットのみが立っている場合の値 \(m\) を管理しておくことで，\(dp_1(i, b) \leftarrow dp_1(i, b) + 1\) および \(dp_2(i, b) \leftarrow dp_2(i, b) + m\) などのように更新できます（この遷移をする場合は，\(i\) ビット目を立てない選択をしたことに対応することに注意してください．特に，\(b, m\) の更新タイミングを誤ると誤った遷移となります）．

\(N\) の popcount が \(K\) である場合は \(dp_2(L, K) + N\) が，そうでない場合は \(dp_2(L, K)\) が答えです．計算量は \(O(LK)\) です．