Bit Counting (UVa Live Archive North America - Southeast - 2010/2011)

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4864

問題

f(x):=xの2進数表記で1の個数という関数を考える。Ni=f(Ni-1)とするとこの数列は1に収束する。このとき、初めて1になったiをKとする。[LO,HI]の区間でK=Xとなるような数値は何個あるか？
1<=LO<=HI<=10^18
0<=X<=10

解法

方針としてはN1のKの値がX-1となるような物の数を考える。こうすると問題が、[1,HI]の間である個数の1が立っている数値の個数を数える問題になる。
まず、[1,64]くらいまでの数値に関してKが何になるかのテーブルを作っておく。次に、calc(depth, bind, hi, bits, x)という関数を作る。この関数は今まで1が立った個数がbitsの時にdepthより下のビットだけを使ってbindがtrueの時はhiまで、falseの時は任意の数値でK=xとなるような物の個数を返す関数である。これはbindがfalseの時にメモ化が出きるのでO(log(hi))で計算できる。あとは1の場合に注意すれば解ける。