桁DP

基本

N以下の値の全探索をDP化したもの。

「今見ている場所(上から何桁目)」「N未満が確定したかどうか」を最低限添え字に持つ。

その二つを基本として、添え字を加えていく形になる。例えば、「0以外の値をこれまでに使ったか？」など

4または9を含まない数字を数え上げる。4または9を使ったか？を添え字として持つ。

dで割ったあまりを添え字として持つ。

前半部分は使いまわせる。

想定解は桁DPじゃないらしい。

Aと等しい/Aより小さい/Aより大きい　を添え字として持つ。

各桁の和を添え字として持つ。

各桁の和をDで割ったあまりを添え字に持つ。

(過去問の提出にアクセスできない場合を考え、一番典型的な実装であるこの問題のコードをここに置いておく)

code:cpp

using mint = modint1000000007;

void _main(){

STR(s);

LL(d);

ll n = s.length();

rep(i,n){

rep(j,2){

rep(k,d){

rep(nx,(j?10ll:D+1)){

}

}

}

}

}