桁DP
基本的には左の桁から順に決めていく。
N以下なのか、N桁以下なのか → 添字で対応
数そのものなのか、桁和なのか → 遷移に影響
メモ化再帰の方が書きやすいものや、周期性を利用した方が簡潔に求められるものある。
$ N桁以下の非負整数で、$ Dで割った余りが$ dとなるものの数を求めよ。
$ DP\lbrack i \rbrack \lbrack j \rbrack = $ i桁目まで決めたときに$ Dで割った余りが$ jとなるものの個数。
DPテーブルはサイズ$ (N+1) * D、$ DP\lbrack 0 \rbrack \lbrack 0 \rbrack = 1で初期化。
遷移は配るDPで
$ \begin{array}{ll}DP\lbrack i+1 \rbrack \lbrack (10*j + p) \% D \rbrack \mathrel{+}{=} DP\lbrack i \rbrack \lbrack j \rbrack & \{p \in \mathbb Z: 0 \leq p \leq 9\} \end{array}
もちろん周期性を利用して割り算でも解けるが、DPだといろいろ条件がついた時にも対応できる。
例題
$ N以下の非負整数で、桁和を$ Dで割った余りが$ dとなるものの数を求めよ。
$ DP\lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack = $ i桁目まで決めたときに、$ Dで割った余りが$ jとなるものの個数。それを$ Nを超えないことが確定しているかで場合分け。$ (k \in \{0, 1\})
DPテーブルはサイズ$ (|N| + 1) * D * 2、$ DP\lbrack 0 \rbrack \lbrack 0 \rbrack \lbrack 0 \rbrack = 1で初期化。
遷移は配るDPで、
$ k = 1のとき
$ \begin{array}{ll}DP\lbrack i+1 \rbrack \lbrack (j + p) \% D \rbrack \lbrack 1 \rbrack \mathrel{+}{=} DP\lbrack i \rbrack \lbrack j \rbrack \lbrack 1 \rbrack & \{p \in \mathbb Z: 0 \leq p \leq 9\} \end{array}
$ k = 0のとき、$ Nの$ i桁目を$ N\lbrack i \rbrackとして、
$ \left\{\begin{array}{ll}\:\: DP\lbrack i+1 \rbrack \lbrack (j + N\lbrack i \rbrack) \% D \rbrack \lbrack 0 \rbrack \mathrel{+}{=} DP\lbrack i \rbrack \lbrack j \rbrack \lbrack 0 \rbrack & \\\begin{array}{ll}DP\lbrack i+1 \rbrack \lbrack (j + p) \% D \rbrack \lbrack 1 \rbrack \mathrel{+}{=} DP\lbrack i \rbrack \lbrack j \rbrack \lbrack 0 \rbrack & \{p \in \mathbb Z: 0 \leq p < N\lbrack i \rbrack\} \end{array} \end{array}\right.
本題とはズレるが3次元以上のDPはin-place DP で書けないか考慮した方がよい。ちなみにこれは$ iと$ i+1だけ保存すればよいので2次元で書ける。 例題
その他の例題