题解 | #游游的9的倍数#

关于这种比较小的模数计数，一般可以给dp多加一个状态，也就是当前的数模特定值之后为多少。

对于本题，我们可以定义定义代表了从前位中选出的数模后值为，那么有如下状态转移方程：

• 情况1，不选当前数:
• 情况2，选当前数: ，其中是第位数的值。

其中basecase为，其他.

需要特别注意的是，空数组的值也为0，最后需要扣掉。

import sys

if __name__ == '__main__':
    s = input().strip()
    n = len(s)
    MOD = 10 ** 9 + 7
    f = [[0] * 9 for _ in range(n + 1)]
    f[0][0] = 1
    for i in range(n):
        for j in range(9):
            f[i + 1][j] = f[i][j]
            f[i + 1][j] = (f[i + 1][j] + f[i][(j - int(s[i])) % 9]) % MOD
    print(f[n][0] - 1)