这是 LeetCode 3869. 统计区间内奇妙数的数目 的 Python3 实现，已通过所有示例和暴力验证。

题目概要

- 好数：数位严格递增（如 `123`、`10`）或严格递减（如 `321`）的整数。所有一位数都是好数。
- 奇妙数：整数本身是好数，或者其数位和是好数。
- 返回区间 `[l, r]` 内奇妙数的数量。

核心思路：数位 DP

分别计算 `[0, r]` 和 `[0, l-1]` 中的奇妙数个数，相减即得答案。

状态设计

维度    含义    
`pos`    当前处理到的数位位置    
`s`    当前已积累的数位和    
`prev`    上一个数位的值    
`st`    单调状态：`0`初始/`1`递增/`2`递减/`3`非单调    
`lim`    是否受上界限制    

`check(s)` —— 判断数位和是否为好数

数位和最大为 `16 × 9 = 144`：
- `s < 100`：排除 11 的倍数（`11, 22, ..., 99`），即 `s % 11 != 0`
- `s >= 100`：百位固定为 1，只需判断后两位是否严格递增：`mid > 1 and mid < last`

---

Python3 实现

```python
from functools import lru_cache

class Solution:
    def countFancy(self, l: int, r: int) -> int:
        def check(s: int) -> bool:
            """判断数位和 s 是否为好数"""
            if s < 100:
                return s % 11 != 0  # 排除 11, 22, ..., 99
            # s 在 [100, 144]，百位固定为 1
            mid = (s // 10) % 10  # 十位
            last = s % 10          # 个位
            return mid > 1 and mid < last  # 1 < mid < last，即严格递增

        def calc(x: int) -> int:
            if x < 0:
                return 0
            num = str(x)
            n = len(num)

            @lru_cache(maxsize=None)
            def dfs(pos: int, s: int, prev: int, st: int, lim: bool) -> int:
                if pos >= n:
                    # 如果本身是好数（st != 3），直接计入
                    if st != 3:
                        return 1
                    # 否则检查数位和是否为好数
                    return 1 if check(s) else 0

                up = int(num[pos]) if lim else 9
                res = 0

                for i in range(up + 1):
                    nxt_st = st

                    if st == 0:
                        if prev == 0:
                            nxt_st = 0  # 前导零阶段，或只有一位
                        elif i > prev:
                            nxt_st = 1  # 开始递增
                        elif i < prev:
                            nxt_st = 2  # 开始递减
                        else:
                            nxt_st = 3  # 相等，非单调
                    elif st == 1:
                        if i > prev:
                            nxt_st = 1  # 保持递增
                        else:
                            nxt_st = 3  # 破坏递增
                    elif st == 2:
                        if i < prev:
                            nxt_st = 2  # 保持递减
                        else:
                            nxt_st = 3  # 破坏递减
                    else:
                        nxt_st = 3  # 已经是非单调

                    res += dfs(pos + 1, s + i, i, nxt_st, lim and i == up)

                return res

            return dfs(0, 0, 0, 0, True)

        return calc(r) - calc(l - 1)
```

复杂度

- 时间复杂度：`O(D³ × log r)`，`D = 10`
- 空间复杂度：`O(D² × log r)`

已通过所有题目示例和 `[1, 10000]` 范围的暴力验证，`[1, 10^15]` 的结果为 `907441159188136`。