HDU 4352 XHXJ's LIS：數位 DP 求區間內 LIS 長度為 K 的數個數

題目大意

查詢區間 [L, R] 中，有多少整數的「自身十進制數字序列的最長上升子序列 (LIS) 長度」等於 K。多測試案例，L, R ≤ 10¹⁸（約 18 位），K ≤ 10。

核心觀察

• 數字的十進制位最多 18 位，每位 0~9。
• LIS 長度 ≤ 10（數字 0~9 共 10 種）。
• 可用**狀態壓縮**：10 位二進制數 `mask` 表示 LIS 中已出現的數字集合。實際上需維護「以每個數字結尾的 LIS 長度」，但因數字域極小 (0~9)，可用 `mask` 表示「哪些數字已被用作 LIS 元素」，並通過預計算 `next[mask][d]` 得到加入數字 d 後的新 mask。

狀態定義

dp[pos][mask][len] = 處理到第 pos 位（從低到高），已用數字集合為 mask，當前 LIS 長度為 len 的方案數。
但實際代碼用 `dp[len][mask][lis]` 其中 `len` 為剩餘位數，`mask` 為已用集合，`lis` 為目標 K（固定），避免重複計算。

預計算 `next[mask][d]`

對於當前集合 `mask`，加入數字 `d`：
- 若 `d` 已在 `mask` 中 → 不改變 LIS 長度，但需更新「結尾最小值」邏輯。實際上用「貪心構造 LIS」的性質：維護每個長度的最小結尾值。因數字域極小，可直接模擬：在 `mask` 表示的序列中插入 `d`，計算新 LIS 長度與新集合。
代碼中 `find_nex` 實現：從 `d` 向上找第一個在 `mask` 中的數字 `i`，將 `i` 替換為 `d`（模擬 patience sorting 替換），若無則加入 `d`。新 mask 對應新 LIS 長度 = `popcount(new_mask)`。

數位 DP 遞歸

ll dfs(int pos, int mask, bool leadZero, bool tight) {
    if (pos == 0) return (popcount(mask) == K);
    if (!tight && memo[pos][mask][K] != -1) return memo[pos][mask][K];
    int up = tight ? digits[pos] : 9;
    ll ans = 0;
    for (int d = 0; d <= up; ++d) {
        int nmask = (leadZero && d == 0) ? 0 : next[mask][d];
        ans += dfs(pos-1, nmask, leadZero && d==0, tight && d==up);
    }
    if (!tight) memo[pos][mask][K] = ans;
    return ans;
}

複雜度

• 狀態：位數 ≤ 19，mask 2¹⁰ = 1024，K ≤ 10。約 19 × 1024 × 11 ≈ 2×10⁵ 狀態。
• 每狀態轉移 10 次。總操作 ~2×10⁶，極快。

關鍵點

• **LIS 狀態壓縮**：利用數字域小 (0~9) 將 LIS 狀態壓縮為 10-bit mask。
• **預計算轉移**：`next[mask][d]` 離線構造，遞歸中 O(1) 轉移。
• **前導零處理**：`leadZero` 標記，前導零不計入 mask。
• **記憶化**：`tight=0` 時記憶化，`tight=1` 不記憶（受上界限制）。

總結

HDU 4352 是「數位 DP + LIS 狀態壓縮」的精妙結合。核心創新在於將 LIS 狀態壓縮為 10-bit mask 並預計算轉移，使數位 DP 狀態數極小。此技巧適用於所有「數字序列 LIS 相關屬性」的數位 DP 問題。