Day 163-Q2 — 2026-09-28 — 桁和で割り切れる数の個数（桁 DP。割る数＝桁和が最後まで決まらないので、桁和 s を外側で固定して s 回 DP する）

📋 コピーimport sys
from operator import add


def count_for(digits, s):
    """[0, N] のうち 桁和 = s かつ s で割り切れる数の個数"""
    L = len(digits)
    # dp[r][m]: N より確実に小さいと決まった状態で、桁和が r、s で割った余りが m の個数（r <= s）
    dp = [[0] * s for _ in range(s + 1)]
    ts, tm = 0, 0                          # N と先頭が一致している唯一の状態の (桁和, 余り)
    shift10 = [(10 * m) % s for m in range(s)]
    for i in range(L):
        nd = digits[i]
        # 1) 余り m → 10m（桁を 1 つずらす）を先に済ませる
        base = [[0] * s for _ in range(s + 1)]
        for r in range(s + 1):
            row = dp[r]
            if not any(row):
                continue
            b = base[r]
            for m in range(s):
                v = row[m]
                if v:
                    b[shift10[m]] += v
        # 2) 次の桁 d を置く: 桁和 r → r+d、余り m → m+d（リストの回転＋要素ごとの和）
        new = [[0] * s for _ in range(s + 1)]
        lo = s - 9 * (L - 1 - i)           # 残りの桁を全部 9 にしても s に届かない桁和は捨てる
        for d in range(10):
            for r in range(max(0, lo - d), s + 1 - d):
                b = base[r]
                if not any(b):
                    continue
                dd = d % s
                rot = b[-dd:] + b[:-dd] if dd else b
                new[r + d] = list(map(add, new[r + d], rot))
        # 3) 先頭一致の状態から N の桁より小さい d を置くと「確実に小さい」側へ移る
        if ts <= s:
            for d in range(nd):
                if lo <= ts + d <= s:
                    new[ts + d][(tm * 10 + d) % s] += 1
        ts += nd
        tm = (tm * 10 + nd) % s
        dp = new
    res = dp[s][0]
    if ts == s and tm == 0:
        res += 1                           # N 自身
    return res


def main():
    n = int(sys.stdin.readline())
    digits = list(map(int, str(n)))
    print(sum(count_for(digits, s) for s in range(1, 9 * len(digits) + 1)))


main()