題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟢 ABC387C Snake Numbers

Problem Statement

題目簡述

對於一個不少於 1010 的正整數，如果它的最高位數字嚴格大於後面每一位數字，則稱為 Snake Number。
給定區間 [L,R][L, R]，請計算其中有多少個 Snake Number。

Constraints

約束條件

  • 10≤L≤R≤101810 \le L \le R \le 10^{18}
  • 所有輸入皆為整數

思路：數位 DP

題目要統計一個很大的整數區間，右界可到 101810^{18}，因此不可能逐一檢查每個數字。條件本身只和「最高位」以及「後續每一位是否更小」有關，很適合用數位 DP 依照十進位表示逐位構造。

Question

如果從高位到低位生成一個數字，什麼時候能判斷它仍然可能是 Snake Number？

一旦最高位確定，後面所有數位都必須嚴格小於最高位。也就是說，構造過程只需要記住「最高位是多少」以及「目前是否仍貼著區間上下界」。

複雜度分析

  • 設 D=⌊log⁡10R⌋+1D = \lfloor \log_{10} R \rfloor + 1 為數位長度，B=10B = 10 為十進位基底。
  • 時間複雜度：O(D⋅B⋅22⋅B)=O(D⋅B2)\mathcal{O}(D \cdot B \cdot 2^2 \cdot B) = \mathcal{O}(D \cdot B^2)。
    • 狀態為 (i,top,limit_low,limit_high)(i, top, limit\_low, limit\_high)，共有 O(D⋅B⋅22)\mathcal{O}(D \cdot B \cdot 2^2) 個；每個狀態枚舉下一位數字 dd，最多 BB 種。
  • 空間複雜度：O(D⋅B⋅22)=O(D⋅B)\mathcal{O}(D \cdot B \cdot 2^2) = \mathcal{O}(D \cdot B)，即記憶化狀態數量。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from functools import cache


def solve():
    l, r = map(int, input().split())

    high = list(map(int, str(r)))
    n = len(high)
    low = list(map(int, str(l).zfill(n)))  # 補前導零，使 low 和 high 對齊

    @cache
    def dfs(i: int, top: int, limit_low: bool, limit_high: bool) -> int:
        if i == n:
            return 1 if top > 0 else 0

        # 第 i 個數位可以從 lo 枚舉到 hi
        # 如果對數位還有其它約束，應該只在下面的 for 迴圈做限制，不應修改 lo 或 hi
        lo = low[i] if limit_low else 0
        hi = high[i] if limit_high else 9

        res = 0
        for d in range(lo, hi + 1):
            if top == 0:
                res += dfs(i + 1, d, limit_low and d == lo, limit_high and d == hi)
            elif d < top:
                res += dfs(i + 1, top, limit_low and d == lo, limit_high and d == hi)
        return res

    ans = dfs(0, 0, True, True)
    dfs.cache_clear()
    print(ans)


if __name__ == "__main__":
    solve()