桁DPと呼ばれるらしい。ある数以下の整数を対象とするとき、上の桁から見ていって、境界ギリギリかどうかによって取り得る値の範囲が変わる。$N=4567$とする。(考慮しなくてよい)次の桁の範囲が限られるか、自由かで、分けて状態を持つ。データ桁DPでよく出てくる構造は、以下。ある数字の個数ただ今回は単純なので、こんなんでもいい。範囲加算が必要なので、累積和を用いる。数字の範囲が「自由」か「制限」かで分類する。桁目は0~9の任意の値を取る。遅いので、いもす法を使って高速化する。$N_i$(Nのi桁目の数字)より小さいような数が、これになる。一致してないといけないので)当然1通り。上と同様に累積和を使う。して、遷移が完了する。一致する数が、これになる。パターン数は1通りとわかっているのでDP配列に状態数を管理する必要は無い。上記の「制限→自由」の際の更新に用いるので桁和だけ更新しておく。大きさのものを作り、D以上の部分は累積和を取った後に移動させる。これには0も入っている。以下の整数」の個数を求めるので、1引く。倍数だった場合は1足す。5個が条件を満たす解法DP自体は割と普通だが、持たせる情報に「なるほど」という発想が必要。同じでも残る整数の組によって次に来れる数の個数は異なってくる。管理できる状態数にならない。次のようにすると良いらしい。各項が全て異なる数列の、隣り合う数字の大小を考慮するだけなら、数字の順位のみが重要となる。3,5が使われていて、「1,2,4」の中から2を選び、残りが「1,4」の2つは、その後の状態数は全く同じになるため、区別する必要が無い。遷移$k=N-i$($i$を含めない残りの数字の個数)とする。数字の順位を0-indexとする。