給定區間 [L, R] (R < 2⁶³) 和 K (≤10)，統計區間內數字的「最長嚴格遞增子序列」（LIS）長度恰好為 K 的個數。例如 124 的數位序列 1,2,4 LIS=3。經典數位 DP + 狀態壓縮題。
標準 LIS O(n log n) 算法維護數組 d[len] = 最小尾值。但數位 DP 需要「無序前綴」的狀態合併。關鍵觀察：只需知道「哪些數字出現過」，不需要知道出現順序。因為 LIS 長度等於「出現過的數字集合中最長遞增子序列長度」，而對於數位 0-9，這等價於集合中元素個數（因為可以按值排序構成遞增序列）。
因此狀態 state 為 10 位掩碼，第 i 位為 1 表示數字 i 出現過。__builtin_popcount(state) 即為當前 LIS 長度。
新數字 v 加入集合：
state | (1<作者採用「優化替換」策略：找到集合中第一個 ≥ v 的元素 u，用 v 替換 u（state ^ (1<
ll dfs(int pos, int state, bool tight, bool leading_zero) {
if (pos == -1) return __builtin_popcount(state) == K;
if (!tight && dp[pos][state][K] != -1) return dp[pos][state][K];
int up = tight ? digit[pos] : 9;
ll ans = 0;
for (int d = 0; d <= up; d++) {
int nstate = (leading_zero && d == 0) ? 0 : newstate(state, d);
ans += dfs(pos-1, nstate, tight && d==up, leading_zero && d==0);
}
if (!tight) dp[pos][state][K] = ans;
return ans;
}
pos：當前處理的數位位置（高→低）state：10 位掩碼tight：是否受上界約束leading_zero：是否仍在前導零區（前導零不計入 state）leading_zero=true 時 d=0 不進 state，避免將 00123 視為含 0 影響 LIS。首個非零數字結束前導零。pos≤19, state<1024, K≤10，DP 表 dp[20][1024][11] 約 22 萬項，極小。calc(R) - calc(L-1)。HDU 4352 展示了數位 DP 中「將順序敏感的 LIS 問題轉化為順序不敏感的集合問題」的精妙建模。掌握「狀態壓縮 + 優化替換 + 前導零處理 + 記憶化搜索」完整模板，可解決數位 DP 中各類子序列計數變體。
