ABC135 D - Digits Parade - あっとのTECH LOG

問題原文

問題要旨

数字と ? からなる文字列 $S$ が与えられる。 ? を好きな数字に置き換えてできる整数のうち、 13で割って5余る数はいくつあるか？
ただし、先頭の0は許可される。

$1 \leq |S| \leq 10^{5}$

解法

すごいDPっぽいのでDPを考える。
まず「何番目までみたか？」の情報は基本なので採用。
$dp[i\rbrack := i 番目の文字までみた時に、 13で割ったあまりが5になるような数の通り数$ というDPをまず考える。まぁ普通に無理。

無理な理由を考える。 $S = 278$ として、２文字目まで考えた時に、13で割ったあまりは1。
3文字目まで考えた時のあまりは、5。これは、 ((27 * 10) + 8) % 5 と等しい。
次の数字を見るたびに、いままでの数字のうしろに０をつける →１０倍すると考えるとわかりやすい。
結局、「13で割ったあまりがなんになるか？」の情報もいる。

dpテーブルを考えると、 $dp[i\rbrack[j\rbrack := i 番目の文字までみた時に、 13で割ったあまりが j になるような数の通り数$ となる。　　

遷移に関しては、次の文字を見るたびに今までみてきた数字が左シフトしていくと考えると、
$if S_i != ?$ のとき
$dp[i + 1\rbrack[(j * 10 + S_i) \% 13\rbrack　 += 　 dp[i\rbrack[j\rbrack$
$if S_i == ?$ のとき
$dp[i + 1\rbrack [(j * 10 + k) \% 13\rbrack 　+= 　dp[i\rbrack[j\rbrack 　(kは1から9)$

となる。

実装

S = input()
N = len(S)
MOD = 10 ** 9 + 7

# dp[i][j] := i文字目までみた時に13で割ってj余るような数の通り数
dp = [[0] * 13 for i in range(N + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
    for j in range(13):
        if s != '?':
            dp[i + 1][((j * 10) + int(s)) % 13] += dp[i][j]
            dp[i + 1][((j * 10) + int(s)) % 13] %= MOD
        else:
            for k in range(10):
                dp[i + 1][((j * 10) + k) % 13] += dp[i][j]
                dp[i + 1][((j * 10) + k) % 13] %= MOD

print(dp[-1][5] % MOD)

感想

良い問題！！！右に数字が追加されていく → いままでのを10倍みたいなのを、パッと出せるようになりたいな