https://atcoder.jp/contests/abc154/tasks/abc154_e

NN の上 ii 桁をつなげた数を N(i)N(i) とする。 NN の上から ii 桁目を NiN_i とする。NN の桁数を ll とする。

dp[i,k,0]={n∈Z∣n<N(i), n の 0 でない数字の数が k}dp[i,k,0] = \{ n \in \mathbb{Z} \mid n < N(i) ,\ n \text{ の } 0 \text{ でない数字の数が } k \} dp[i,k,1]={n∈Z∣n=N(i), n の 0 でない数字の数が k}dp[i,k,1] = \{ n \in \mathbb{Z} \mid n = N(i) ,\ n \text{ の } 0 \text{ でない数字の数が } k \} とすると、求めたいのは dp[l,K,0]+dp[l,K,1]dp[l,K,0] + dp[l,K,1] である。

dp[i,0,0]=1,dp[i,0,0]=1, (0 に対応)

dp[1,1,0]=N1−1,dp[1,1,0] = N_1-1, (1,…,N1- 1に対応)

dp[1,k,0]=0(k≥2),dp[1,k,0]= 0 (k \ge 2),

dp[1,k,1]=1,dp[1,k,1] = 1,

遷移を考えると

dp[i+1,k,0]=dp[i,k,0]+9⋅dp[i,k−1,0](k≥1,Ni+1=0),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⋅dp[i,k−1,0]+dp[i,k,1]+(Ni+1−1)dp[i,k−1,1](k≥1,Ni+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](Ni+1=0),dp[i+1,k,1] = dp[i,k,1] (N_{i+1} = 0),

dp[i+1,k,1]=dp[i,k−1,1](Ni+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というらしい。