3624. Number of Integers With Popcount-Depth Equal to K II
解題說明
Number of Integers With Popcount-Depth Equal to K II
題目描述：定義一個整數的「popcount 深度」為：反覆對該數取 popcount（二進位中 1 的個數）直到結果為 1 所需的次數。例如，7 = 111₂ → popcount(7) = 3 = 11₂ → popcount(3) = 2 = 10₂ → popcount(2) = 1，深度為 3。給定查詢 [l, r, k]，計算在 [l, r] 範圍內 popcount 深度恰好為 k 的整數個數。
解題思路：首先觀察 popcount 深度的性質。對於 64 位元整數，popcount 最大為 64，popcount(64) <= 6，所以深度最多 5-6 層。關鍵是計算 [1, n] 中 popcount 深度為 k 的數的個數（利用前綴和：答案 = f(r, k) - f(l-1, k)）。
對於計算 f(n, k)：深度為 0 的數只有 1。深度為 1 的數是 popcount 為 1 的數（2 的冪）。深度為 d 的數是 popcount 值的深度為 d-1 的數。因此需要用數位 DP：枚舉 [1, n] 中每個數的 popcount 值 p，然後檢查 depth(p) == k-1。
C++ 解法
複雜度分析
時間複雜度：O(Q * B²) — Q 為查詢數，B 為位元數（最多 63）。每個查詢需要枚舉所有可能的 popcount 值（最多 63 個），每個值的數位 DP 為 O(B)。
空間複雜度：O(Q) — 儲存結果。數位 DP 使用 O(B) 空間。
虛擬碼
1. Precompute getDepth(x): repeatedly apply popcount until x == 1, count steps
2. For counting numbers in [1, n] with exactly `pc` set bits:
a. Use combinatorial digit DP: scan bits of n from high to low
b. At each '1' bit, count combinations of placing remaining bits in lower positions
3. For countDepthK(n, k):
a. For each popcount value pc from 1 to 63:
- If getDepth(pc) == k-1: add countWithPopcount(n, pc)
4. Answer each query [l, r, k] = countDepthK(r, k) - countDepthK(l-1, k)其他解法
預處理 + 前綴和（小範圍）：若數值範圍不大，可以直接預計算每個數的 popcount 深度，用前綴和回答查詢。O(maxN) 預處理，O(1) 查詢。
分塊 + 線段樹：將數值範圍分塊，每塊預計算各深度的計數。支援動態更新，但實作複雜。
延伸思考
- 如果定義的「深度」改為反覆取數字和（digit sum）而非 popcount，問題如何變化？
- 若查詢帶有更新（修改某個位置的數值），如何用線段樹支援？
- popcount 深度的分佈有什麼數學規律？最大深度是多少？