ABC135 D
D問題
桁DPを使用する
1の位,10の位,100の位...と桁毎にパターンを数えあげていく
10の位のパターン = 1の位のパターン + 10の位のパターン
100の位のパターン = 10の位のパターン + 100の位のパターン
python3だとTLEになっちゃうのでpypyで提出
pypyでもこまめに値を小さくしないとTLEになる
ss = input() # 13で割ったあまり0~12のパターンを格納する dp = [0] * 13 # 0 % 13 = 0なのであまり0の初期値1 dp[0] = 1 # 出力条件 mod = 10 ** 9 + 7 # 対象の位 mul = 1 # 文字列の後ろから順に数える for s in ss[::-1]: # 次のdpを用意 next_dp = [0] * 13 if s == '?': # 文字列'0'~'9' for num in range(10): # あまり0~12 for i in range(13): # パターン数を更新 next_dp[(num * mul + i) % 13] += dp[i] # 値を小さくする next_dp[(num * mul + i) % 13] %= mod else: num = int(s) # ?の場合と同様 for i in range(13): next_dp[(num * mul + i) % 13] += dp[i] next_dp[(num * mul + i) % 13] %= mod # 1の位->10の位->100の位... mul *= 10 # 値を小さくする mul %= 13 dp = next_dp # あまりが5となるパターン数 print(dp[5])