这是 LeetCode 3448. 统计可以被最后一个数位整除的子字符串数目 的 Python3 实现。

解题思路

核心观察：子字符串的最后一位只有 `1~9` 这 9 种可能（不能为 0）。对于每个位置 `i`，我们想知道以 `s[i]` 结尾的子串中，有多少能被 `s[i]` 整除。

动态规划：
- 设 `dp[d][rem]` 表示以当前位置结尾的子串中，模 `d` 余 `rem` 的子串数量。
- 遍历每个字符 `digit` 时，创建新的 `new_dp`：
  - 扩展：对于每个模数 `d` 和余数 `rem`，之前模 `d` 余 `rem` 的子串在末尾追加 `digit` 后，新的余数为 `(rem * 10 + digit) % d`。
  - 新建：`digit` 单独作为一个子串，余数为 `digit % d`。
- 如果 `digit != 0`，则 `ans += dp[digit][0]`，即统计以当前字符结尾、能被 `digit` 整除的子串数量。

复杂度：
- 时间：`O(9 × 9 × n) = O(n)`，其中 `n = len(s)`
- 空间：`O(9 × 9) = O(1)`

Python3 代码

```python
class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        # dp[d][rem] 表示以当前位置结尾的子串中，模 d 余 rem 的子串数量
        # d 范围 1~9，rem 范围 0~d-1，统一开 10×10
        dp = [[0] * 10 for _ in range(10)]

        for c in s:
            digit = ord(c) - ord('0')
            new_dp = [[0] * 10 for _ in range(10)]

            # 枚举所有可能的模数 d（1~9）
            for d in range(1, 10):
                # 转移：将之前以当前位置前一个字符结尾的子串扩展
                for rem in range(d):
                    new_dp[d][(rem * 10 + digit) % d] += dp[d][rem]
                # 单独当前字符作为一个新的子串
                new_dp[d][digit % d] += 1

            dp = new_dp
            # 当前字符作为子串最后一位，若不为 0，则统计模 digit 余 0 的数量
            if digit != 0:
                ans += dp[digit][0]

        return ans
```

验证

已通过全部示例验证：
- `s = "12936"` → `11`
- `s = "5701283"` → `18`
- `s = "1010101010"` → `25`

下载链接

[LeetCode 3448 Python3 实现](sandbox:///mnt/agents/output/leetcode_3448.py)