題目連結:
題目大意:
定義 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 ;當 m = 2 ,結果為 1 ; m = 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 之類的)
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。