Introduction to DP on digits ( 桁DP / 數位統計 )

pekempey.hatenablog.com
苦手だったけどpekempeyさんの記事見てよく理解できました、ありがとうございます。pekempeyさんの書き方をモノマネする事になるけどそこはどうか許してください（汗）。
Atcoder Beginner Contest 29 pD.
Submission #631749 - AtCoder Beginner Contest 029 | AtCoder
こんな感じですね。数が大きすぎる場合( > 1e9 )、普通に dp( x ) = dp( x - 1 ) とかの関係式でDP はできませんね、時間はまだしも、メモリ制限を超えます。こういう時には桁DP を使いましょう。桁数+ 1、あるいは- 1 の関係を探せば、桁数と比例する複雑度が願えられます。転移に必要な情報や最後に知りたい結果などはインデックスと一緒に組み込み、答えを出す時は互いに関係のない状態かつ計算範囲内の方法数の和を計算すれば楽勝です。

実装には僕も rep マクロを使うことにしました、できれば使わない身でしたが５、６まで行く多重ループ見たらあきらめました。
DPの順序は最高位から最下位まで行って自分から自分を使う状態を更新していく書き方はわかりやすくてあまり間違えません。最大数は確定してるので列挙する数は必ずその最大数以下にする事、それと「ここまで来てちょうどその最大数に張りつけるように決めてたのか、それともどっかでもう後ろの数字をどう決めてもいいように小さく決めていたのか」を[ 2 ] で記録すれば楽です。

この書き方で注意する事：
•　使う前にちゃんと0 で埋める事、計算は全部 += で更新してるから、もし最初から0 じゃなかったら問題が起こります。
•　境界は大抵 way[0][0]..[0]、「未満かどうか」も含めて全てが0 の時、答えは1 になります。
•　000..0 を含めてしまうので邪魔にだったら特別に考慮します。