https://atcoder.jp/contests/abc154/tasks/abc154_e
\(N\) の上 \(i\) 桁をつなげた数を \(N(i)\) とする。 \(N\) の上から \(i\) 桁目を \(N_i\) とする。\(N\) の桁数を \(l\) とする。
\(dp[i,k,0] = \{ n \in \mathbb{Z} \mid n < N(i) ,n の 0 でない数字の数が k \}\) \(dp[i,k,1] = \{ n \in \mathbb{Z} \mid n = N(i) ,n の 0 でない数字の数が k \}\) とすると、求めたいのは \(dp[l,K,0] + dp[l,K,1]\) である。
\(dp[i,0,0]=1, \) (0 に対応)
\(dp[1,1,0] = N_1-1,\) (1,…,N1- 1に対応)
\(dp[1,k,0]= 0 (k \ge 2),\)
\(dp[1,k,1] = 1,\)
遷移を考えると
\(dp[i+1,k,0] = dp[i,k,0]+9\cdot dp[i,k-1,0] (k \ge 1, N_{i+1}=0),\)
\(dp[i+1,k,0] = dp[i,k,0]+9\cdot dp[i,k-1,0]+dp[i,k,1]+(N_{i+1}-1)dp[i,k-1,1] (k \ge 1, N_{i+1}\neq 0),\)
\(dp[i+1,k,1] = dp[i,k,1] (N_{i+1} = 0),\)
\(dp[i+1,k,1] = dp[i,k-1,1](N_{i+1} \neq 0),\)
https://atcoder.jp/contests/abc154/submissions/31951620
調べてみたらこういうものを桁DPというらしい。