https://atcoder.jp/contests/abc154/submissions/14394556
- 桁DPは状態 EQ (equal: 同値) と LT (less than: 未満) を持つのが定跡
- 初期値は dp[0][0][state::EQ] = 1;
- 繰り返しは rep(j, 1, Size(N)) rep(k, 0, K + 1)
- 更新は if (k + 1 <= K) dp[j][k + 1][state::LT] += dp[j - 1][k][state::LT] * 9; など
- 出力は dp.back()[K][state::EQ] + dp.back()[K][state::LT];
dp[j][k][st] := 状態stにおけるj桁目までにk個[0, K]の0以外の数字を持つようなXの組み合わせ数 と定義し、各桁に対して下記のようなDP式で処理する。
- stについて [st::EQ]から[st::LT]へと状態が変わるDP式
- stについて [st::EQ]や[st::LT]のまま状態が変わらないDP式
- kについて [k]から[k+1]になるDP式
- kについて [k]のまま不変のDP式
細かい注意点として N[j] = 0 のとき X[j] < N[j] が存在しないので、N[j] = 0 と N[j] ≠ 0 で場合分けすると良いかと思う。また、Nの先頭にダミーを入れておくと実装が楽になると思う。
