c688. 數一數二 - 高中生程式解題系統

內容

$定義 b (n) 為 n 以二進位表示時1的個數， f_{i} (m) 為 {n | m \leq n \leq 2 m - 1, b (n) = i} 的元素個數，請回答以下問題。$

$1. 對於 i 和 r ，請求出 f_{i} (2^{r}) 和 f_{i} (2^{r} + 1) 。 (i, r \leq 60)$

$2. 給定 i, m 和 f_{i} (m) ，請求出 f_{i} (m + 1) 。 (i, m, f_{i} (m) \leq 10^{18})$

$3. 對於 m ，請求出 f_{2} (m) 。 (m \leq 10^{18})$

$4. 對於 i 和 r ，試決定最小的 m_{r} 及最大的 m_{r}^{'} 使得 f_{i} (m_{r}) = f_{i} (2^{r}) = f_{i} (m_{r}^{'}) 。 (2 \leq i \leq 60, r \leq 60)$

$5. 對於 i 和 m ，請求出 f_{i} (m) 。 (i, m \leq 10^{18})$

$(i, r, m, m_{r}, m_{r}^{'} 皆為非負整數。)$

輸入說明

第一行有兩個正整數 $Q, T$ ，代表問的是第 $Q$ 個問題且有 $T$ 筆詢問。

接下來 $T$ 行分別有若干以空格分開的數字，範圍和意義如題敘所述。

輸出說明

依序輸出每次詢問的答案。

範例輸入 #1

範例輸入一：
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 1

範例輸出二：
55
55
55

範例輸出三：
1
5
8
11

範例輸出四：
4 5
7 9
13 17

範例輸出五：
165
330
462

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (14%): 0.5s , <1M
公開測資點#1 (14%): 0.5s , <1M
公開測資點#2 (14%): 1.0s , <10M
公開測資點#3 (14%): 2.0s , <50M
公開測資點#4 (14%): 0.5s , <1M
公開測資點#5 (15%): 2.0s , <50M
公開測資點#6 (15%): 2.0s , <50M

提示：

部分值域限制與原題不同。
TRML 的原題中並沒有 5.，且 4. 本來有 i = 3, r >= 2 的限制，請注意邊界處理。

解決 5 顯然就能回答 1 2 3 ，但請試著想想數學上更精簡的解法。

測資點 $0 : Q = 1$
測資點 $1 \sim 2 : Q = 2$
測資點 $3 : Q = 3$
測資點 $4 : Q = 4$
測資點 $5 \sim 6 : Q = 5$

對於所有測資， $T \leq 1000000$ 。

標籤:

出處:

TRML 2018 [管理者： icube (!@#$%^&*()_...) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」