DP S
ある数K以下の自然数で、条件を満たすものがいくつあるか、という問題
素朴にK個の数を調べることはKがやたらでかいのでできない前提
>桁DPはもらうDPよりも配るDPの方が圧倒的に書きやすい
なるほど、以前試してバグらせた時はもらう実装でやってた
まずはシンプルに「K以下の自然数の個数を数え上げる」をDPで考える
57以下の自然数の数を数えている
ゼロを含むので「57未満が57個、イコールが1個」となっている
「先頭i桁」を定義域とし、そこまでで「K以下である数」「イコールKである数」の個数を値とするDP
ところで「イコールKである数」は常に1なのだからテーブルで持つ必要はないよね
解説などではテーブルで持ってるものが多くて、その方が複雑な問題だと実装の都合が良いことがあるのかな
今回の問題では追加の条件「Dで割り切れる」のチェックのためにDで割ったあまりごとに数え分けているが、僕の実装では「イコールK」にはテーブルを用意しなかった
pythondef solve(N, D):
less = [0] * D
equal = 0
for digit in N:
new_less = [0] * D
for new_digit in range(10):
for d in range(D):
new_less[(d + new_digit) % D] += less[d]
if new_digit < digit:
new_less[(equal + new_digit) % D] += 1
for d in range(D):
new_less[d] %= MOD
less = new_less
equal += digit
equal %= D
ret = less[0]
ret -= 1 # for x = 0
if equal == 0: # for x = N
ret += 1
return ret % MODold version
pythondef solve(K, D):
K = [x - ord("0") for x in K]
N = len(K)
less = [[0] * D for i in range(N + 1)]
border = 0
for i in range(N):
for j in range(10):
for d in range(D):
less[i][(d + j) % D] += less[i - 1][d]
less[i][(d + j) % D] %= MOD
if j < K[i]:
less[i][(border + j) % D] += 1
border += K[i]
border %= D
ret = less[N - 1][0] - 1
ret += (border == 0)
return ret % MODRelated Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁DP×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]