Digits Parade [AtCoder Beginner Contest 135 D]

https://atcoder.jp/contests/abc135/tasks/abc135_d

前提知識

• 桁DP

解説

https://atcoder.jp/contests/abc135/submissions/6588492

桁DPしていこう。
dp[dgt][mo] := dgt桁目まで確定していて、そこまでで13で割ったあまりがmoである組み合わせ
?でないときは、その数にしかできないため、その数を使う。
?であるときは、0～9を全て試して遷移させよう。

string S;
int N;
mint dp[101010][13];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();

    dp[0][0] = 1;
    rep(dgt, 0, N) rep(mo, 0, 13){
        if (S[dgt] == '?') {
            rep(nxt, 0, 10) {
                dp[dgt + 1][(mo * 10 + nxt) % 13] += dp[dgt][mo];
            }
        }
        else {
            dp[dgt + 1][(mo * 10 + S[dgt] - '0') % 13] += dp[dgt][mo];
        }
    }

    cout << dp[N][5] << endl;
}