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

解题思路

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

动态规划：
- 设 `dp[d][rem]` 表示以当前位置结尾的子串中，模 `d` 余 `rem` 的子串数量。
- 遍历每个字符 `digit` 时，创建新的 `newDp`：
  - 扩展：对于每个模数 `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 = s.length()`
- 空间：`O(9 × 9) = O(1)`

Java 代码

```java
class Solution {
    public long countSubstrings(String s) {
        long ans = 0;
        // dp[d][rem] 表示以当前位置结尾的子串中，模 d 余 rem 的子串数量
        // d 范围 1~9，rem 范围 0~d-1，统一开 10×10
        int[][] dp = new int[10][10];

        for (char c : s.toCharArray()) {
            int digit = c - '0';
            int[][] newDp = new int[10][10];

            // 枚举所有可能的模数 d（1~9）
            for (int d = 1; d <= 9; d++) {
                // 转移：将之前以当前位置前一个字符结尾的子串扩展
                for (int rem = 0; rem < d; rem++) {
                    newDp[d][(rem * 10 + digit) % d] += dp[d][rem];
                }
                // 单独当前字符作为一个新的子串
                newDp[d][digit % d]++;
            }

            dp = newDp;
            // 当前字符作为子串最后一位，若不为 0，则统计模 digit 余 0 的数量
            if (digit != 0) {
                ans += dp[digit][0];
            }
        }

        return ans;
    }
}
```

验证

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

下载链接

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