https://atcoder.jp/contests/abc135/submissions/15552119
- 桁DPで処理する
- 初期値は dp[0][0] = 1
- 繰り返しは rep(i, 1, Size(S))
- 更新は if (S[i] == '?') rep(j, 0, 13) rep(k, 0, 10) dp[i][(j * 10 + k) % 13] += dp[i - 1][j] など
- 出力は dp.back()[5]
|S|が最大桁あるので桁DPで処理する。dp[i][m] := i桁目の剰余がmになる組み合わせの数とする。S[i] = s のとき、dp[i][(s + m) % 13] += dp[i-1][m] の遷移をして、i-1桁目の組み合わせ数をi桁目の組み合わせ数に加算していく処理をする。1桁前の情報を次の桁に活かせる理由は、割り算の筆算で考えると分かりやすい。
if (S[i] == '?') rep(j, 0, 13) rep(k, 0, 10) dp[i][(j * 10 + k) % 13] += dp[i - 1][j];
else rep(j, 0, 13) dp[i][(j * 10 + CtoL(S[i])) % 13] += dp[i - 1][j];
S[i] = ? のとき、剰余の範囲[0, 13)とS[i]の範囲[0, 10)全て遷移する必要があるので、二重ループになることに注意する。Sの先頭にダミーの'0'を追加してdp[0][0] = 1で初期化すると実装が楽になる。計算量はになる。