ABC336 E - Digit Sum Divisible

atcoder.jp

問題

• N以下の正整数のうち、各桁の総和で割り切れるものはいくつありますか？

成約

• $ 1 \leq N \leq 10^{14}$

思考

• 成約がぶっ飛びすぎ
• 桁DPを使う、らしい
  • 暫くは「N以下で、◯◯の個数！」みたいなパターンでマッチして良さそう
• 上の桁から、「そこまでずっとNと一致している」「N以下が確定した」に分けて遷移していくイメージ
• まだ言語化できるまでしっかり飲み込めてないので、もう少し類題解く必要あり :TODO
• 今回は桁和がいろんなパターンあるねぇ…1から、$9 \times 14$まで…
  • じゃあ126回桁DPすれば良いだろ！！！！！！とかいうどうにもパワープレイが模範解答、らしい…
    • 黒ココアさんの脳内メモリには3次元以上の配列は乗らないため、頑張って2次元配列で収めるとかいうこっちもパワープレイ

コード

N = input()

def ketaDP(ketawa):
    # dp[i][j] := 桁和がi、かつ、iで割った余りがjである数字の個数
    prev_dp0 = [[0]*ketawa for i in range(ketawa+1)] # 未確定（＝いっしょ）
    prev_dp1 = [[0]*ketawa for i in range(ketawa+1)] # 確定（＝ちっちゃい）
    prev_dp0[0][0] = 1

    for keta in range(len(N)):
        next_dp0 = [[0]*ketawa for i in range(ketawa+1)]
        next_dp1 = [[0]*ketawa for i in range(ketawa+1)]

        # 既にちっちゃい確定組は、次もちっちゃい確定組！
        for i in range(ketawa+1):
            for j in range(ketawa):
                for next_num in range(10):
                    if i + next_num > ketawa:continue # 桁和は超えちゃダメ
                    next_dp1[i + next_num][(j*10 + next_num)%ketawa] += prev_dp1[i][j]

        # 未確定組は、次にちっちゃい組に移るパターンと、未確定組のままのパターンが有りけり
        # ここはちっちゃい組に移るパターン
        for i in range(ketawa+1):
            for j in range(ketawa):
                for next_num in range(int(N[keta])):
                    if i + next_num > ketawa:continue
                    next_dp1[i + next_num][(j*10 + next_num)%ketawa] += prev_dp0[i][j]

                # ここは未確定組のままのパターン
                if i + int(N[keta]) <= ketawa:
                    next_dp0[i + int(N[keta])][(j*10 + int(N[keta]))%ketawa] += prev_dp0[i][j]
        prev_dp0 = next_dp0
        prev_dp1 = next_dp1

    # dp[i][j] := 桁和がi、かつ、iで割った余りがjである数字の個数
    # なので、桁和がketawa、かつ、ketawaで割った余りが0である数字の個数！
    # 未確定組にもいるパターン（Nがketawaで割り切れるパターン）はあるので、忘れずに！
    return prev_dp0[ketawa][0] + prev_dp1[ketawa][0]

ans = 0
# 桁和が1~9*14のパターンでそれぞれ該当する個数を足し合わせる！
for i in range(1,9*14+1):
    ans += ketaDP(i)
print(ans)