題目連結：
題目大意：
定義 b(n) 為 n 以二進位表示法之 1 的個數，而 Fi(m) 為 { n | m ≦ n ≦ 2m - 1 且 b(n) = i } 之元素個數。現在有五個問題：
1：給定 i、r ，求 Fi(2 ^ r) 以及 Fi(2 ^ r + 1)。（i 、 r ≦ 60）
2：給定 i、m 和 Fi(m) ，求 Fi(m + 1)。（i、 m 、 Fi(m) ≦ 10 ^ 18）
3：給定 m ，求 F2(m)。（m ≦ 10 ^ 18）
4：給定 i 、 r ，求出最小的可能的 mr 以及最大的可能 mr' ，使得 Fi(mr) = Fi(2 ^ r) = Fi(mr')。（2 ≦ i ≦ 60 ， r ≦ 60）
5：給定 i 、 m ，求出 Fi(m)。（i 、 m ≦ 10 ^ 18）
（以上的 i 、 r 、 m 、 mr 、 mr' 皆為非負整數）
每一組測試資料開頭會有兩個正整數 Q 、 T ，代表接下來要解第 Q 個問題，且有 T 列的相應輸入。（ T ≦ 1,000,000）
範例輸入：
範例輸入一：
1 3
1 0
1 1
1 2
範例輸入二：
2 3
3 2017 55
3 2018 55
3 2019 55
範例輸入三：
3 4
2
20
201
2018
範例輸入四：
4 3
3 2
3 3
3 4
範例輸入五：
5 3
4 2018
5 2018
6 2018
範例輸出：
範例輸出一：
1 1
1 1
1 1
範例輸出二：
55
55
55
範例輸出三：
1
5
8
11
範例輸出四：
4 5
7 9
13 17
範例輸出五：
165
330
462
解題思維：
首先，以上題目是從 2018 年的 TRML 之競賽題目中的「思考題」出來的，因此可以先去此網站查看此題，了解一些背景知識（因為本題是 TRML 思考題的延伸）。
首先，問題 1：
因為 2 ^ r 的二進位表示法為 100…… 共有 r 個 0。而 2 ^ (r + 1) - 1 為 111…… ，共 r + 1 個 1 。因此，Fi(2 ^ r) = C(r, i - 1)。其中 C(n, k) 代表著 n 個物品取 k 個的組合數。
而 Fi(2 ^ r + 1) 的數字範圍為 2 ^ r + 1 ～ 2 ^ (r + 1) + 1，與前一項少了 2 ^ r ，但是多了 2 ^ (r + 1) 、 2 ^ (r + 1) + 1 兩個數字。
但是我們可以只考慮 2 ^ (r + 1) + 1 的 1 之個數（2 個）是否等於 i ，也就是判斷 i 是否等於 2 。如果等於就把前一項（即 Fi(2 ^ r)）的結果 + 1 。
問題 2：
Fi(m + 1) 的數字範圍為 m + 1 ～ 2m + 1，少了 m ，但多了 2m 、 2m + 1 兩個數字。因此我們只需要判斷這三個數字的二進位表示法。
但是我們可以看出來，如果 m 有 i 個 1 ，那麼 2m 也有 i 個 1，兩者一加一減會抵消；m 沒 i 個 1 ，那麼 2m 也沒有 i 個 1，兩者不影響答案。
因此我們只需要判斷 2m + 1 是否有 i 個 1 。
問題 3：
因為 Fi(m + 1) = Fi(m) + 1 的充分條件為 2m + 1 有 i 個 1 （從問題 2 可以看出）。把 i = 2 帶入，可以發現當 b(m) = 1 時， Fi(m + 1) = Fi(m) + 1。
也就是：當 m ＝ 0、1 ，結果為 0 ；當 ｍ ＝ 2 ，結果為 1 ； ｍ ＝ 3 、 4 ，結果為 2 ……
結論：當 2 ^ (n - 1) < m ≦ 2 ^ n 時，結果為 n 。
問題 4：
把思考題之第 12 小題的 b(m) = 2 換成 b(m) = i - 1 去思考即可。但是要小心數據的邊界之問題。
問題 5：
根據思考題第 10 、 11 小題，我們得知了：
Fi(2m) = Fi-1(m) + Fi(m) 。
Fi(2m + 1) = Fi-1(m) + Fi(m) +（b(m) 是否等於 i - 1。是的話為 1 ；不是則為 0 ）。
因此，對於任意數 m ，我們可以建立起大小為 i + 1 的 DP 陣列，用來儲存初始狀態 Fk(1) 之值（k 屬於 0 ～ i ）。然後利用位元運算，判斷何時要乘以 2 ，何時要乘以 2 再加 1 ，並照著以上的關係式推出下一項。
當數字推演到 m 時，此時 DP[i] 便是儲存 Fi(m) 之值。（一樣要小心邊界問題，例如 i > 60 之類的）
達人