多組查詢,每組給定區間 [s, e],求區間內不含數字 4、也不含連續子串 "62" 的整數個數。s, e ≤ 10^6?實際上 e 可達 10^9,需數位 DP。
dp[pos][prev]:從高位到低位處理到第 pos 位(0 為最低位),前一位數字為 prev(0~9,10 表示無前一位/前導零),滿足條件的方案數。
狀態轉移:枚舉當前位 dig (0~9),若 dig==4 跳過;若 prev==6 && dig==2 跳過;否則累加 dp[pos-1][dig]。
因無上界限制,可預計算 dp[len][firstDigit]:長度為 len、最高位為 firstDigit 的合法數個數。
dp[0][0]=1;
dp[i][j] = Σ dp[i-1][k] (k≠4, 且不滿足 j==6&&k==2)。
返回 [0, x] 合法數個數。將 x 分解為數位數組 digit[](高位在前)。從高位向低位枚舉:
對第 i 位,枚舉 d = 0 ~ digit[i]-1,若合法則累加 dp[i][d]。
若 digit[i] 本身非法(==4 或 前位==6且本位==2),中斷。
最後返回累加和。
答案 = solve(e) - solve(s-1)。