問題
$0$ ~ $9$ または $?$ からなる文字列 $S$ の $?$ を数字に置き換えてできる整数のうち $13$ で割って $5$ あまる数の個数を求めよ。
解説
上から $i - 1$, $i$ 桁を $13$ で割った余りをそれぞれ $r$, $k$ とすると、$\mathrm{mod}\ 13$ において $10$ の逆元が$4$ なので
$$
\begin{aligned}
10 r + k &= j \\
r &= 4(j - k)
\end{aligned}
$$
よって、$S[i - 1] = k$ の場合は、上から $i$ 桁について $13$ で割って $j$ あまる個数は上から $i - 1$ 桁について $13$ で割って $4(j - k)$ あまる個数に等しい。
一方、$S[i - 1] = \ ?$ の場合は $k = 0$ から $9$ までの和になる。
$DP[i][j]$ を上から $i$ 桁について $13$ で割って $j$ あまる個数とすると、遷移式は
$$
DP[i][j]=
\begin{cases}
DP[i-1][4(j - k)] \ \ (S[i - 1] = k) \\
\sum_{k = 0}^{9}DP[i-1][4(j - k)] \ \ (S[i - 1] = \ ?)
\end{cases}
$$
実装
S = input() n = len(S) p = 10**9+7 DP = [[0]*13 for i in range(n+1)] DP[0][0] = 1 for i in range(1, n+1): for j in range(13): if S[i-1] == '?': DP[i][j] = sum([DP[i-1][(4*(j-k)) % 13] for k in range(10)]) % p else: k = int(S[i-1]) DP[i][j] = DP[i-1][(4*(j-k)) % 13] print(DP[n][5])
