桁DPで巨大な範囲を数える

0からNを全部調べられなくても、桁ごとに「上限と一致中か」と必要な性質を持てば数えられます。

言語：Python / 計算量：O(桁数 × D × 10)

前提：DPは「同じ続きをまとめる」

考え方

1. 状態を位置・上限一致・数字和の余りなどで定義。
2. 一致中ならその桁は上限の数字まで。
3. 先頭の0と数0そのものの扱いを決めます。

具体例

N=20、数字和が3の倍数の正整数は3,6,9,12,15,18 の6個です。

実装

N="20";D=3
dp={(True,0):1}
for c in N:
    nd={}
    for (tight,r),count in dp.items():
        limit=int(c) if tight else 9
        for d in range(limit+1):
            key=(tight and d==int(c),(r+d)%D)
            nd[key]=nd.get(key,0)+count
    dp=nd
print(sum(v for (t,r),v in dp.items() if r==0)-1)

注意する条件

先頭0を許す場合、0自体も1通りとして数えられます。正整数限定なら除外します。

確認問題

1から20で数字和が3の倍数の個数は？

実装課題

文字列 N (1≤N≤10^100) と D (1≤D≤100) が別行。1..N で数字和がDの倍数の個数を10^9+7で割った余り。

入力:
20
3
出力:
6

N=input().strip();D=int(input());p=10**9+7
dp={(True,0):1}
for c in N:
    nd={}
    for (tight,r),count in dp.items():
        for d in range((int(c) if tight else 9)+1):
            key=(tight and d==int(c),(r+d)%D)
            nd[key]=(nd.get(key,0)+count)%p
    dp=nd
print((sum(v for (t,r),v in dp.items() if r==0)-1)%p)

読了の記録・下書き・メモへ

関連する公式資料・課題