行吟信息科技（上海）有限公司校招算法工程师笔试经验——求职精灵（finsight.work）

设 dp[r] 表示「扫描到当前位置时，余数为 r 的非空子序列个数」。逐个字符推进，对数字 d 有三条来源：不选（沿用原 dp）、单独成序列（余数 d % k 加 1）、拼在已有子序列后面（余数 (r×10 + d) % k 累加 dp[r]）。答案取最终的 dp[0]。

MOD = 10**9 + 7
def count_divisible(s, k):
    dp = [0] * k
    for ch in s:
        d = int(ch)
        ndp = dp[:]                    # 不选：沿用上一轮
        ndp[d % k] = (ndp[d % k] + 1) % MOD    # 单独成序列
        for r in range(k):             # 拼在已有子序列后面
            if dp[r]:
                nr = (r * 10 + d) % k
                ndp[nr] = (ndp[nr] + dp[r]) % MOD
        dp = ndp
    return dp[0]

复杂度：时间 O(nk)，空间 O(k)（滚动数组）。
作答要点：①必须用 dp 的副本更新，否则同一个字符会被重复使用；②k = 1 时所有非空子序列都满足，可用来快速自测；③数字含 0 时，前导零是否影响计数需先向面试官确认口径。

关键洞察是：时间与金钱两个目标相互耦合，不能拆成两次独立最短路，必须做联合建模。
做法分四步：

1. 因为每条边耗时都是 1，先按步数做 BFS，求出 s、t 到每个点的最短步数
2. 枚举会合点 m，两人到达 m 的时间取 max，记为 L
3. 在「不超过 L 步」的约束下，求 s→m、t→m 的最小金钱（分层图上的 DP）
4. 从 m 到终点跑一次 Dijkstra，边权用「时间 + 金钱」的联合代价，对所有 m 取最小值

核心：分层图 + 双源会合 + 联合代价。
作答要点：①说清为什么不能分开算——分开会把两条互不兼容的路径拼在一起，得到不可行的解；②联合代价的权重如何确定，要先和面试官确认时间与金钱的换算关系；③先到的同学能否等待、等待是否计入时间成本，会直接改变答案。