AtCoder Beginner Contest 135 D - Digits Parade

atcoder.jp
典型的なdpだが解けなかった。
いかにも競プロっぽいので、こういうのが解けるようになれば楽しそう。

問題概要

数字と?で構成される文字列Sがある。
?を数字に置き換えてできる整数のうち、13で割って5あまる数は何通りあるか。

制約

len(S) <= 10^5

解法

dp[i][j]を、i文字目まで見たとき、13でわった余りがjになる数の総数とする。
i+1文字目への遷移は、i+1文字目の数字がkとすると、
dp[i+1][(j*10+k)%13] += dp[i][j]
をj = 0,1,....12としたものになる。
（例えばdp[2][7]は2文字目まで見てあまりが7の総数なので、3文字目が5ならば、70+5を13で割ったあまりのところにそれを足してやる）
i+1文字目が?のときはkを0から9まで動かす。

# ABC 135 D - Digits Parade

S = input()
N = len(S)
dp = [[0 for i in range(13)] for j in range(N+1)]
# dp[i][j] := i文字目まで見たときに13でわった余りがjになる総数

MOD = 10**9 + 7
dp[0][0] = 1

for i in range(1,N+1):
    if S[i-1] == "?":
        for j in range(13):
            for k in range(10):
                dp[i][(j*10+k)%13] += dp[i-1][j]
                dp[i][(j*10+k)%13] %= MOD
    else:
        t = int(S[i-1])
        for j in range(13):
            dp[i][(j*10+t)%13] += dp[i-1][j]
            dp[i][(j*10+t)%13] %= MOD

print(dp[N][5])