Problem:
 Score : 500 points    Problem Statement Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.      Constraints  1 \leq N < 10^{100}  1 \leq K \leq 3         Input Input is given from Standard Input in the following format:  N  K       Output Print the count.        Sample Input 1 100
1      Sample Output 1 19  The following 19 integers satisfy the condition:   1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100        Sample Input 2 25
2      Sample Output 2 14  The following 14 integers satisfy the condition:   11,12,13,14,15,16,17,18,19,21,22,23,24,25        Sample Input 3 314159
2      Sample Output 3 937       Sample Input 4 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3      Sample Output 4 117879300

Solution (Python):
n=input()
k=int(input())


dp=[[[0]*2 for i in range(k+2)] for j in range(len(n)+1)]
dp[0][0][0]=1


for i in range(len(n)):
  x=int(n[i])
  for j in range(k+1):
    
    if x==0:
      dp[i+1][j][0]+=dp[i][j][0]
    else:
      dp[i+1][j+1][0]+=dp[i][j][0]

    dp[i+1][j][1]+=dp[i][j][1]    
    if x!=0:
      dp[i+1][j][1]+=dp[i][j][0]    
    
    dp[i+1][j+1][1]+=dp[i][j][1]*9    

    if x!=0:
      dp[i+1][j+1][1]+=dp[i][j][0]*max(x-1,0)    


print(dp[-1][k][0]+dp[-1][k][1])

Solution (Python):
n=[int(x) for x in list(input())]
l=len(n)
k=int(input())
"""
桁DP
桁数,0でないcount,ギリギリflagでdp
"""
dp = [[[0 for _ in range(2)] for _ in range(k+1)] for _ in range(l+1)]

dp[1][0][0] = 1
dp[1][1][0] = n[0] - 1
dp[1][1][1] = 1
for i in range(2,l+1):
  for j in range(0,min(i,k)+1):
    if j > 0:
      dp[i][j][1] += dp[i-1][j-1][1]*(n[i-1]>0)
      dp[i][j][0] += dp[i-1][j-1][0]*9+dp[i-1][j-1][1]*max(0,n[i-1]-1)
    dp[i][j][1] += dp[i-1][j][1]*(n[i-1]==0)
    dp[i][j][0] += dp[i-1][j][0] + dp[i-1][j][1]*(n[i-1]>0)
    
print(sum(dp[l][k]))

Solution (Python):
n=input()
kk=int(input())

l=len(n)

dp=[[[0]*2 for _ in range(101)] for _ in range(l+1)]
dp[0][0][0]=1

for i,dig in enumerate(n):
    dig=int(dig)

    for j in range(10):
        for k in range(100):
            nk=k if j==0 else k+1
            if j<dig:
                dp[i+1][nk][1]+=dp[i][k][0]+dp[i][k][1]
            elif j==dig:
                dp[i+1][nk][1]+=dp[i][k][1]
                dp[i+1][nk][0]+=dp[i][k][0]
            else:
                dp[i+1][nk][1]+=dp[i][k][1]

print(dp[l][kk][0]+dp[l][kk][1])

Solution (Python):
"""
桁DPで解ける
dp[i][j][k][l] => i桁目まで見る。i桁目がjであるような数字の数。kは0でない数の個数のメモ。lは未満フラグ。
"""
N = input()
K = int(input())
dp = [[[[0]*(2) for _ in range(5)]for _ in range(10)]for _ in range(len(N))]


x = int(N[0])
for i in range(x+1):
    if i == 0:
        dp[0][i][0][1] += 1
    else:
        if i<x:
            flag = 1
        else:
            flag = 0
        dp[0][i][1][flag] += 1

for i in range(len(N)-1):
    x = int(N[i+1])
    for j in range(10):
        for k in range(4):
            for l in range(2):
                if l:
                    r = 10
                else:
                    r = x+1
                for m in range(r):
                    if l==0 and m==x:
                        flag = 0
                    else:
                        flag = 1
                    
                    if m == 0:
                        cnt = k
                    else:
                        cnt = k+1
                    dp[i+1][m][cnt][flag] += dp[i][j][k][l]

ans = 0
for j in range(10):
    ans += sum(dp[-1][j][K])

print(ans)

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    dp[lower][i][j] - if number of ways such that one of the digit is lower and contains j non-zero digits
    """
    N = input()
    length = len(N)
    K = read_int()
    dp = [
        [[0 for _ in range(K+1)] for _ in range(length+1)]
        for _ in range(2)
    ]
    dp[False][0][0] = 1
    for i in range(1, length+1):
        dp[True][i][0] = 1
        for j in range(1, K+1):
            dp[True][i][j] = 9*dp[True][i-1][j-1]+dp[True][i-1][j]
            if int(N[i-1]) > 0:
                dp[True][i][j] += dp[False][i-1][j-1]*(int(N[i-1])-1)+dp[False][i-1][j]
                dp[False][i][j] = dp[False][i-1][j-1]
            else:
                dp[False][i][j] = dp[False][i-1][j]
    return dp[True][length][K]+dp[False][length][K]


if __name__ == '__main__':
    print(solve())

Solution (Python):
import math
import sys
sys.setrecursionlimit(10**9)


def comb(n, r):  
    if r < 0 or r > n:
        return 0
    else:
        n1 = math.factorial(n)
        n21 = math.factorial(n - r)
        n22 = math.factorial(r)
        ans = n1 // (n21 * n22)
        return ans


"""
solve(i, k, smaller)
:= i桁目以降について、0以外の値を残りk個使用可能という状況を考える。
このときi桁目までの部分が「等しい」か「strictに小さくなっている」かを
smallerフラグによって分岐する。
"""


def solve(i, k, smaller):  

    

    if i == N:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    if smaller == True:
        return comb(N - i, k) * pow(9, k)

    else:
        if S[i] == "0":
            return solve(i + 1, k, False)
        else:
            """
            ex. S = 314159　の場合
            000000〜099999 := a
            100000〜299999 := b
            300000〜314159 := c　のように場合分け
            """
            a = solve(i + 1, k, True)
            b = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
            c = solve(i + 1, k - 1, False)
            return a + b + c



S = input()

N = len(S)
K = int(input())

ans = solve(0, K, False)
print(ans)

Solution (Python):
def zeroTrim(s):
    while s[0] == '0':
        if len(s) == 1:
            break
        s = s[1:]
    return s

N = input()
K = int(input())

def calc(N, K):
    digit = len(N)
    res = 0

    if K == 1:
        if digit > 1:
            res += (digit - 1) * 9
        res += int(N[0])
    elif K == 2:
        if digit <= 1:
            return 0
        if digit > 2:
            res += 9 * 9 * (digit - 1) * (digit - 2) // 2
        for i in range(int(N[0])-1):
            res += calc('9'*(digit-1), 1)
        res += calc(zeroTrim(N[1:]), 1)
    else:
        if digit <= 2:
            return 0
        if digit > 3:
            res += 9 * 9 * 9 * (digit - 1) * (digit - 2) * (digit - 3) // 6
        
        for i in range(int(N[0])-1):
            res += calc('9'*(digit-1), 2)
        res += calc(zeroTrim(N[1:]), 2)
    return res

print(calc(N, K))

Solution (Python):
s=input()
m=int(input())
n=len(s)
if n==1:
  print([0,int(s)][m==1])
  exit()
dp=[[[0]*2 for _ in range(m+1)] for _ in range(n)]
dp[0][0][1]=1
dp[0][1][1]=int(s[0])-1
dp[0][1][0]=1
for i in range(1,n):
  for j in range(m+1):
    if j:
      dp[i][j][1]+=9*dp[i-1][j-1][1]
      if s[i]!='0':
        dp[i][j][0]+=dp[i-1][j-1][0]
        dp[i][j][1]+=(int(s[i])-1)*dp[i-1][j-1][0]
    if s[i]=='0':dp[i][j][0]+=dp[i-1][j][0]
    dp[i][j][1]+=dp[i-1][j][1]
    if s[i]!='0':dp[i][j][1]+=dp[i-1][j][0]
print(sum(dp[-1][-1]))

Solution (Python):
import math



    

def solve(sN):
    dp = [[[0]*105 for _ in range(4)] for _ in range(2) ] 
    
    dp[0][0][0]=1 
    for i in range(len(sN)):
        for j in range(4):
            for k in range(2):
                nd = int(sN[i])
                for d in range(10):
                    ni = i+1;nj=j;nk=k
                    if d != 0: 
                        nj +=1
                    if nj > K:
                        continue
                    if k ==0:
                        if d > nd:
                            continue
                        if d < nd:
                            nk = 1
                    dp[nk][nj][ni]+=dp[k][j][i]
    ans = dp[0][K][len(sN)]+dp[1][K][len(sN)]
    return ans

sN = input()
K = int(input())
lenN = len(sN)
ans = solve(sN)
print(ans)

Solution (Python):
import math
def isMore(N,K):
    
    if len(N) < K:
        return 0
    
    if K>=1:
        tmp = (9-int(N[0]))*fact[len(N)-1]//((fact[len(N)-K])*(fact[K-1]))*(9**(K-1))
        
        if len(N)==1:
            return tmp
        
        elif len(N)>1 and N[0]=='0':
            return tmp + isMore(N[1:],K)
        
        elif len(N)>1 and N[0]!='0':
            return tmp + isMore(N[1:],K-1)
    
    if K == 0:
        return 0

N = input()
K = int(input())
lenN = len(N)
fact = [1]*101
for i in range(1,101):
    fact[i] = fact[i-1]*i

ans = fact[lenN]//((fact[lenN-K])*fact[K])*(9**K)
ans -= isMore(N,K)
print(ans)

Solution (Python):
import math
def isMore(N,K):
    
    if len(N) < K:
        return 0
    
    if K>=1:
        tmp = (9-int(N[0]))*fact[len(N)-1]//((fact[len(N)-K])*(fact[K-1]))*(9**(K-1))
        if len(N)==1:
            return tmp
        elif len(N)>1 and N[0]=='0':
            return tmp + isMore(N[1:],K)
        elif len(N)>1 and N[0]!='0':
            return tmp + isMore(N[1:],K-1)
    if K == 0:
        return 0

N = input()
K = int(input())
lenN = len(N)
fact = [1]*101
for i in range(1,101):
    fact[i] = fact[i-1]*i

ans = fact[lenN]//((fact[lenN-K])*fact[K])*(9**K)
ans -= isMore(N,K)
print(ans)

Solution (Python):
n = input()
a = list(n)
k = int(input())
n = len(a)
for i in range(n):
    a[i] = int(a[i])
dp = [[[0 for i in range(2)] for i in range(k+2)]for i  in range(n)]
dp[0][0][0] = 1
dp[0][1][0] = a[0]-1
dp[0][1][1] = 1
for i in range(n-1):
    for j in range(k+1):
        if a[i+1] == 0:
            dp[i+1][j][1] += dp[i][j][1]
            dp[i+1][j][0] += dp[i][j][0]
            dp[i+1][j+1][0] += dp[i][j][0]*9
        else:
            dp[i+1][j][0] += dp[i][j][0]+dp[i][j][1]
            dp[i+1][j+1][0] += dp[i][j][1]*(a[i+1]-1)+dp[i][j][0]*9
            dp[i+1][j+1][1] += dp[i][j][1]
print(dp[n-1][k][0]+dp[n-1][k][1])

Solution (Python):
n = str(input())
k = int(input())
l = len(n)

def f(dig, under, num):
  if num > l - dig: return 0
  if num == 0: return 1
  if dig == l-1:
    if under: return int(n[dig])
    else: return 9
  if under:
    if n[dig] == '0':
      res = f(dig+1, True, num)
      
      return res
    else:
      res = f(dig+1, False, num)
      if int(n[dig]) > 1:
        res += (int(n[dig])-1) * f(dig+1, False, num-1)
      res += f(dig+1, True, num-1)
      
      return res
  else:
    res = f(dig+1, False, num)
    res += 9 * f(dig+1, False, num-1)
    
    return res

ans = f(0, True, k)
print(ans)

Solution (Python):
def calc(a,D,K):
  if K==1:
    return a+(D-1)*9
  elif K==2:
    return (a-1)*(D-1)*9 + (D-1)*(D-2)//2*81
  else:
    return (a-1)*(D-1)*(D-2)//2*81 + (D-1)*(D-2)*(D-3)//6*729

N=input()
K=int(input())
D = len(N)
score=0
for i,a in enumerate(N):
  if a!="0":
    score+=calc(int(a),D-i,K)
    K-=1
  if K==0:
    break
print(score)

Solution (Python):
import sys

input = sys.stdin.readline


def solve(N, K, L):
    dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(L + 1)]
    dp[0][0][0] = 1
    for i in range(L):
        D = N[i]
        for j in range(2):
            d_max = 9 if j == 1 else D
            for k in range(K + 1):
                if k < K:
                    for d in range(d_max + 1):
                        dp[i + 1][int(j or (d < D))][k + int(d > 0)] += dp[i][j][k]
                else:
                    dp[i + 1][j][k] += dp[i][j][k]

    return dp[L][0][K] + dp[L][1][K]


def main():
    N = list(map(int, input().rstrip()))
    K = int(input())

    L = len(N)
    ans = solve(N, K, L)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


import numpy as np

input = sys.stdin.readline



def solve(N, K, L):
    dp = np.zeros(shape=(L + 1, 2, K + 1), dtype=np.int64)
    dp[0][0][0] = 1
    for i in range(L):
        D = N[i]
        for j in range(2):
            d_max = 9 if j == 1 else D
            for k in range(K + 1):
                if k < K:
                    for d in range(d_max + 1):
                        dp[i + 1][int(j or (d < D))][k + int(d > 0)] += dp[i][j][k]
                else:
                    dp[i + 1][j][k] += dp[i][j][k]

    return dp[L][0][K] + dp[L][1][K]


def main():
    N = np.array(list(input().rstrip()), dtype=np.int64)
    K = int(input())

    L = N.shape[0]
    ans = solve(N, K, L)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


def solve_K_1(N):
    S = str(N)
    d = len(S)
    return 9 * (d - 1) + int(S[0])


def solve_K_2(N):
    if N <= 99:
        return N - solve_K_1(N)
    S = str(N)
    d = len(S)
    res = 0
    res += 81 * (d - 1) * (d - 2) // 2
    res += 9 * (d - 1) * (int(S[0]) - 1)
    x = 0
    for i in range(1, d):
        if S[i] != "0":
            x = int(S[i])
            break
    i += 1
    res += x + 9 * (d - i)
    return res


def solve_K_3(N):
    if N <= 999:
        return N - solve_K_1(N) - solve_K_2(N)
    S = str(N)
    d = len(S)
    res = 0
    for n in range(3, d):
        res += 729 * (n - 1) * (n - 2) // 2
    res += 81 * (d - 1) * (d - 2) // 2 * (int(S[0]) - 1)
    res += solve_K_2(int(S[1:]))
    return res


def main():
    N = int(input())
    K = int(input())

    if K == 1:
        ans = solve_K_1(N)
    elif K == 2:
        ans = solve_K_2(N)
    elif K == 3:
        ans = solve_K_3(N)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

from functools import lru_cache

N = int(sys.stdin.readline().rstrip())
K = int(sys.stdin.readline().rstrip())


@lru_cache(None)
def F(N, K):
    """(0以上）N以下で、0でないものがちょうどK個"""

    assert N >= 0  

    if N < 10:  
        if K == 0:  
            return 1  
        if K == 1:
            return N  
        return 0  

    q, r = divmod(N, 10)  

    ret = 0
    if K >= 1:
        
        ret += F(q, K - 1) * r  
        ret += F(q - 1, K - 1) * (9 - r)

    
    ret += F(q, K)
    return ret


print(F(N, K))

Solution (Python):
import sys


def resolve(in_):
    N = next(in_).strip()
    K = int(next(in_))

    
    dp0 = [[0] * (K + 1) for _ in range(len(N) + 1)]
    dp0[0][0] = 1
    
    dp1 = [[0] * (K + 1) for _ in range(len(N) + 1)]

    ord_zero = ord('0')
    for i, s in enumerate(map(lambda s: s - ord_zero, N)):
        for j in range(K + 1):
            dp1[i + 1][j] += dp1[i][j]
            if s > 0:
                dp1[i + 1][j] += dp0[i][j]
            else:
                dp0[i + 1][j] += dp0[i][j]
            if j < K:
                
                dp1[i + 1][j + 1] += dp1[i][j] * 9
                
                dp1[i + 1][j + 1] += dp0[i][j] * max(0, (s - 1))
                
                if s > 0:
                    dp0[i + 1][j + 1] += dp0[i][j]

    return dp0[len(N)][K] + dp1[len(N)][K]


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):

def resolve():
    S = input()
    K = int(input())
    N = len(S)

    
    
    
    
    

    dp = [[[0]*2 for _ in range(4)] for _ in range(N+1)]
    dp[0][0][0] = 1

    for i in range(N):
        for j in range(4):
            for smaller in range(2):
                now = int(S[i])
                for d in range(10):
                    ni = i+1
                    nj = j
                    n_smaller = smaller
                    if d != 0:
                        nj += 1
                    if nj > K:
                        continue
                    if smaller == 0:
                        if d > now: 
                            continue
                        if d < now: 
                            n_smaller = 1
                    dp[ni][nj][n_smaller] += dp[i][j][smaller]
    ans = dp[N][K][0] + dp[N][K][1]
    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n=RD()
	k=II()

	dp=[[[0]*2 for _ in range(k+2)] for _ in range(len(n)+1)]
	

	dp[0][0][0]=1

	for i in range(len(n)):
		now=int(n[i])
		for j in range(k+1):
			
			dp[i+1][j+(now!=0)][0]+=dp[i][j][0]
			dp[i+1][j][1]+=dp[i][j][1]+dp[i][j][0]*(now!=0)
			dp[i+1][j+1][1]+=dp[i][j][1]*9+dp[i][j][0]*(now-1 if now>0 else 0)
		
	print(dp[len(n)][k][0]+dp[len(n)][k][1])

















if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n=RD()
	k=II()

	dp=[[[0]*2 for _ in range(k+2)] for _ in range(len(n)+1)]
	

	dp[0][0][0]=1

	for i in range(len(n)):
		now=int(n[i])
		for j in range(k+1):
			
			dp[i+1][j+(now!=0)][0]+=dp[i][j][0]
			dp[i+1][j][1]+=dp[i][j][1]+dp[i][j][0]*(now!=0)
			dp[i+1][j+1][1]+=dp[i][j][1]*9+dp[i][j][0]*(now-1 if now>0 else 0)
		
	print(dp[len(n)][k][0]+dp[len(n)][k][1])

















if __name__ == "__main__":
	main()

Solution (Python):
import numpy as np

N = list(map(int, input()))
K = int(input())
l = len(N)
if l < K:
    print(0)
    exit()


dp_small = np.zeros((l+1, K+1), dtype=np.int64)
dp_large = np.zeros((l+1, K+1), dtype=np.int64)
dp_large[0, 0] = 1
for d, digit in enumerate(N, 1):
    for k in range(K+1):
        
        dp_small[d, k] += dp_small[d-1, k]
        if digit != 0:
            dp_small[d, k] += dp_large[d-1, k]
            dp_large[d, k] = 0
        else:
            dp_large[d, k] = dp_large[d-1, k]
        if k!=0:
            
            dp_small[d, k] += dp_small[d-1, k-1] * 9
            if digit >= 1:
                dp_small[d, k] += dp_large[d-1, k-1] * (digit-1)
                dp_large[d, k] += dp_large[d-1, k-1]
print(dp_small[l, K] + dp_large[l, K])

Solution (Python):
n = list(map(int, list(input())))
k = int(input())
l = len(n)

ans = 0
if k == 1:
    ans = n[0] + (l - 1) * 9
elif k == 2:
    if l == 1:
        ans = 0
    else:
        for i in range(l - 1):
            p = True
            for j in range(i + 1, l):
                if i == 0 and p:
                    ans += (n[i] - 1) * 9 + n[j]
                elif i == 0:
                    ans += n[i] * 9
                else:
                    ans += 9 * 9
                if n[j] != 0:
                    p = False
else:
    if l <= 2:
        ans = 0
    else:
        for i in range(l - 2):
            p1 = True
            for j in range(i + 1, l - 1):
                p2 = True
                for k in range(j + 1, l):
                    if i == 0 and p1 and p2:
                        ans += (n[i] - 1) * 9 * 9
                        ans += (n[j] - 1) * 9 + n[k] if n[j] != 0 else 0
                    elif i == 0 and p1 and not p2:
                        ans += (n[i] - 1) * 9 * 9 + n[j] * 9
                    elif i == 0 and not p1:
                        ans += n[i] * 9 * 9
                    else:
                        ans += 9 * 9 * 9
                    if n[k] != 0:
                        p2 = False
                if n[j] != 0:
                    p1 = False
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = list(input())
K = int(input())
length = len(N)

dp = [[[0]*2 for _ in range(K+1)] for _ in range(length+1)]
dp[0][0][1] = 1
for i in range(length):
    n = int(N[i])
    for k in range(K+1):
        if k==K:
            dp[i+1][k][0]+=dp[i][k][0]
            if n==0:
                dp[i+1][k][1]+=dp[i][k][1]
            else:
                dp[i+1][k][0]+=dp[i][k][1]
            continue
        for j in range(10):
            if j==0:
                if n==0:
                    dp[i+1][k][0]+=dp[i][k][0]
                    dp[i+1][k][1]+=dp[i][k][1]
                else:
                    dp[i+1][k][0]+=dp[i][k][0]+dp[i][k][1]
            elif j==n:
                dp[i+1][k+1][1]+=dp[i][k][1]
                dp[i+1][k+1][0]+=dp[i][k][0]
            elif j<n:
                dp[i+1][k+1][0]+=dp[i][k][0]+dp[i][k][1]
            else:
                dp[i+1][k+1][0]+=dp[i][k][0]
print(sum(dp[-1][K]))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = input()
n = len(s)
K = inp()
dp = [[[0 for i in range(5)] for j in range(2)] for k in range(n+1)]

dp[0][1][0] = 1
for i,x in enumerate(s):
    x = int(x)
    for k in range(4):
        dp[i+1][0][k] += dp[i][0][k]
        dp[i+1][0][k+1] += dp[i][0][k]*9 + dp[i][1][k]*max(0,(x-1))

        if x != 0:
            dp[i+1][0][k] += dp[i][1][k]
            dp[i+1][1][k+1] = dp[i][1][k]
            if k == 0: dp[i+1][1][k] = 0
        else:
            dp[i+1][1][k] = dp[i][1][k] 
        for j in range(2):
            dp[i+1][j][k] %= mod

    
    
    
print(dp[-1][0][K] + dp[-1][1][K])

Solution (Python):
S = input()
L = len(S)
K = int(input())

dp = [[[0,0] for _ in range(K+1)] for _ in range(L+1)]
dp[0][0][0] = 1
for i,c in enumerate(S):
    c = int(c)
    for k in reversed(range(K+1)):
        for d in range(10):
            nk = k + (d>0)
            if nk > K: continue
            dp[i+1][nk][1] += dp[i][k][1]
            if d > c: continue
            less = int(d < c)
            dp[i+1][nk][less] += dp[i][k][0]
print(sum(dp[-1][-1]))

Solution (Python):
n = input()
k = int(input())
l = len(n)

def k2(l, n):
    ans = 81 * (l - 1) * (l - 2) // 2
    ans += (int(n[0]) - 1) * 9 * (l - 1)
    for i, s in enumerate(n[1:]):
        if s == "0":
            continue
        ans += int(s)
        ans += max((l - i - 2), 0) * 9
        break
    return ans

if k == 1:
    ans = (l - 1) * 9 + int(n[0])
elif k == 2:
    if l == 1:
        print(0)
        exit()
    ans = k2(l, n)
else:
    if l < 3:
        print(0)
        exit()
    ans = 9 ** 3 * (l - 1) * (l - 2) * (l - 3) // 6
    ans += (int(n[0]) - 1) * 81 * (l - 1) * (l - 2) // 2
    n = n[1:]
    n = str(int(n))
    ans += k2(len(n), n)
print(ans)

Solution (Python):
S = input()
N = len(S)
K = int(input())

dp = [[[0] * 2 for _ in range(4)] for _ in range(N + 10)]
dp[0][0][0] = 1

for i, s in enumerate(S):
    nd = int(s)
    for j in range(K+1):
        for k in range(2):
            for d in range(10):
                ni = i + 1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if nk == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk += 1
                dp[ni][nj][nk] += dp[i][j][k]

print(dp[N][K][0]+dp[N][K][1])

Solution (Python):
N = input()
L = len(N)
K = int(input())

dp = [ [ [0]*2 for _ in range(4) ] for _ in range(L+1) ]
dp[0][0][0] = 1
for i in range(L):
  for j in range(K+1):
    for k in range(2):
      nd = int(N[i])
      for d in range(10):
        ni = i+1
        nj = j
        nk = k
        if d != 0: nj += 1
        if nj > K: continue
        if k==0:
          if d > nd: continue
          if d < nd: nk = 1

        dp[ni][nj][nk] += dp[i][j][k]

print(dp[L][K][0] + dp[L][K][1])

Solution (Python):
def calc(a,D,K):
  if K==1:
    return a+(D-1)*9
  elif K==2:
    return (a-1)*(D-1)*9 + (D-1)*(D-2)/2*81
  else:
    return (a-1)*(D-1)*(D-2)/2*81 + (D-1)*(D-2)*(D-3)/6*729

N=str(input())
K=int(input())
D = len(N)
score=0
for i,a in enumerate(N):	
  if a!="0":
    score+=calc(int(a),D-i,K)
    K-=1
  if K==0:
    break
print(int(score))

Solution (Python):
def resolve():
    N = list(input())
    lenN = len(N)
    K = int(input())
    dp = [[[None, None] for _ in range(K+1)] for __ in range(lenN)]

    def rec(i, k, smaller):
        if k==0:
            return 1
        if i>=lenN:
            return 0
        
        if dp[i][k][int(smaller)] is not None:
            return dp[i][k][int(smaller)]
        
        ret = 0
        if smaller:
            ret += rec(i+1, k, True)
            ret += rec(i+1, k-1, True) * 9
        else:
            if N[i] == "0":
                ret += rec(i+1, k, False)
            else:
                ret += rec(i+1, k, True) 
                ret += rec(i+1, k-1, True) * (int(N[i]) - 1) 
                ret += rec(i+1, k-1, False) 
        
        dp[i][k][int(smaller)] = ret
        return ret

    print(rec(0, K, False))
    
    
if __name__ == "__main__":
    resolve()

Solution (Python):


n = int(input())
K = int(input())

def make_list(n):
    N = []
    while(n>0):
        N.append(n%10)
        n = n //10
    N.reverse()
    return N

N = make_list(n)
m = len(N)
dp = [[[ 0 for k in range(K+1)] for j in range(2)] for i in range(m)]  

dp[0][0][0] =  1 
dp[0][0][1] = N[0] - 1 
dp[0][1][0] = 0
dp[0][1][1] = 1 

for i in range(1,m):
    dp[i][0][0] = 1 
    
    for k in range(1,K+1):
        if N[i] == 0:
            dp[i][0][k] = dp[i-1][0][k-1] * 9 + dp[i-1][0][k]
            dp[i][1][k] = dp[i-1][1][k]
        else:
            dp[i][0][k] = dp[i-1][0][k-1] * 9 + dp[i-1][0][k] + dp[i-1][1][k] + dp[i-1][1][k-1] * (N[i] - 1)
            dp[i][1][k] = dp[i-1][1][k-1]

print(dp[m-1][1][K] + dp[m-1][0][K])

Solution (Python):
N = list(map(int, input()))
K = int(input())


dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(len(N) + 1)]
dp[0][0][0] = 1
for i in range(len(N)):
    for j in range(K + 1):
        for is_smaller in range(2):
            for l in range(10):
                if not is_smaller and l > N[i] or l != 0 and j + 1 > K:
                    continue
                i_ = i + 1
                j_ = j
                is_smaller_ = is_smaller

                if l != 0:
                    j_ += 1

                if not is_smaller and l < N[i]:
                    is_smaller_ = 1
                dp[i_][j_][is_smaller_] += dp[i][j][is_smaller]
print(dp[len(N)][K][0] + dp[len(N)][K][1])

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = input()
    K = I()

    dp1 = [[0] * len(N) for _ in range(K + 2)] 
    dp2 = [[0] * len(N) for _ in range(K + 2)] 

    dp1[1][0] = 1
    dp2[0][0] = 1
    dp2[1][0] = int(N[0]) - 1

    for i in range(1, len(N)):
        num = int(N[i])
        for k in range(K+1):
            if num == 0:
                dp1[k][i] += dp1[k][i - 1]
                dp2[k][i] += dp2[k][i - 1]
                dp2[k+1][i] = dp2[k][i - 1] * 9
            else:
                dp1[k + 1][i] += dp1[k][i - 1]
                dp2[k][i] += dp2[k][i - 1] + dp1[k][i - 1]
                dp2[k + 1][i] = dp2[k][i - 1] * 9 + dp1[k][i - 1] * (num - 1)

    print(dp1[K][-1] + dp2[K][-1])

if __name__ == '__main__':
    main()

Solution (Python):

N = input()
K = int(input())

dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(len(N) + 1)]
dp[0][0][0] = 1
for i in range(len(N)):
    n = int(N[i])
    for j in range(2):
        for k in range(K + 1):
            for d in range((9 if j == 1 else n) + 1):
                if k + int(d != 0) <= K:
                    dp[i + 1][j | (d < n)][k + int(d != 0)] += dp[i][j][k]

n_self = int(len(N) - N.count("0") == K)
print(dp[-1][-1][-1] + n_self)

Solution (Python):
S = list(input())
K = int(input())
N = len(S)
dp = [[[0] * 2 for i in range(4)] for i in range(105)]

dp[0][0][0] = 1
for i in range(N):
    nd = int(S[i])
    for j in range(4):
        for k in range(2):
            for d in range(10):
                ni = i+1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

print(dp[N][K][0] + dp[N][K][1])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *




def C(n, r):
	if n < r:
		return 0
	else:
		return factorial(n)//factorial(n-r)//factorial(r)

N = input()
K = INT()

n = len(N)

ans = 0
if K <= n-N.count("0"):
	ans += 1

for i in range(n):
	if N[i] != "0" and 0 < K:
		ans += (int(N[i])-1) * 9**(K-1) * C(n-i-1, K-1) + C(n-i-1, K) * 9**K
		K -= 1

print(ans)

Solution (Python):
import numpy as np

s = input()
n = int(s)
k = int(input())

m = len(s)
dp = np.zeros((m+1, 2, k+2), dtype=np.int64)
dp[0][1][0] = 1
for cs in range(m):
    cn = int(s[cs])
    for ck in range(k+2):
        if ck == k+1:
            nk = ck
        else:
            nk = ck + 1
        dp[cs+1][0][nk] += 9 * dp[cs][0][ck]
        dp[cs+1][0][ck] += dp[cs][0][ck]

        if cn == 0:
            dp[cs+1][1][ck] += dp[cs][1][ck]
        else:
            dp[cs+1][1][nk] += dp[cs][1][ck]
            dp[cs+1][0][nk] += (cn - 1) * dp[cs][1][ck]
            dp[cs+1][0][ck] += dp[cs][1][ck]
print(dp[m][0][k] + dp[m][1][k] )