【ABC135】D - Digits Parade

atcoder.jp

解法

制約的にも桁DPがしたくなる。
そこで次のDPを考える。

dp[i][j] ← 下からi桁目までみた時、13で割った数がjであるような場合は何通りあるか

上からi桁目としてもいいが、計算が楽なので下から見ていくことにした。

次のように遷移する。
ここで、0 ≦ i < |S|, 0 ≦ j < 13, 0 ≦ k < 10 とする。

• S[i]が？のとき
  • dp[i + 1][(j + 10ⁱ * k) MOD 13] += dp[i][j]
• S[i]が？でないとき
  • dp[i + 1][(j + 10ⁱ * S[i]) MOD 13] += dp[i][j]

答えは、dp[|S|][5]になる。

実装

10ⁱを計算するときは、愚直に実装するとO(|S|)になってしまうので、繰り返し二乗法を利用する。
modintを使用できると実装が楽になる。
下の実装のmintはmod 10⁹ + 7、mint13はmod 13 で計算している。

void solve(std::string S){
    reverse(all(S)); // 逆順にする

    // dpテーブル
    vector<vector<mint>> dp(S.size()+1, vector<mint>(13, 0));
    dp[0][0] = 1;

    REP (i, S.size()) {
        if (S[i] == '?') {
            // ?のときは0~9までの場合を全て試す
            REP (j, 10) {
                mint13 cur = modpow((mint13)10, i) * j;
                REP (k, 13) {
                    dp[i + 1][(cur.val + k) % 13] += dp[i][k];
                }
            }
        } else {
            mint13 cur = modpow((mint13)10, i) * (S[i] - '0');
            REP (k, 13) {
                dp[i + 1][(cur.val + k) % 13] += dp[i][k];
            }
        }
    }

    cout << dp[S.size()][5] << endl;
}```