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):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

'''MEMO:

'''

def main(): 
    N = II()
    K = II()

    keta_N = len(str(N))

    ans = 0

    
    if K == 1: ans += min(9, N)
    else: pass
    if N < 10:
        print(ans)
        return

    
    if K == 1:
        for i in range(10, 100, 10):
            if i <= N:
                ans += 1
    elif K == 2:
        for i in range(10, 100, 1):
            if i%10 == 0:
                continue
            elif i <= N:
                ans += 1
    else: pass
    if N < 100:
        print(ans)
        return

    
    if K == 1:
        ans += 9 * (keta_N - 3)
    else:
        for keta in range(3, keta_N):
            if K == 2:
                ans += 9 * (keta-1) * 9
            else:
                ans += (9 * (keta-1) * (keta-2) * 9 * 9)//2

    
    
    if K == 1:
        for i in range(1, 10):
            if i * 10**(keta_N - 1) <= N:
                ans += 1

    elif K == 2:
        for i in range(1, 10):
            for j in range(1, 10):
                for k in range(0, keta_N-1):
                    if i * 10**(keta_N - 1) + j * 10**k <= N:
                        ans += 1

    elif K == 3:
        for i in range(1, 10):
            if i < int(str(N)[0]):  
                ans += ((keta_N - 1) * (keta_N - 2) * 9 * 9)//2
                continue
            elif i > int(str(N)[0]):
                break
            for j in range(1, 10):
                for k in range(0, keta_N-1):
                    for l in range(1, 10):
                        for m in range(0, keta_N-1):
                            if k <= m: continue
                            if i * 10**(keta_N - 1) + j * 10**k + l * 10**m <= N:
                                ans += 1

    print(ans)

main()

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

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




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

for i in range(len(N)):
    num = int(N[i])  
    for x in range(K+1):
        if num == 0:
            dp[i+1][x][0] += dp[i][x][0]
            dp[i+1][x][1] += dp[i][x][1]
            if x >= 1:
                dp[i+1][x][1] += dp[i][x-1][1]*9
        else:  
            dp[i+1][x][1] += dp[i][x][0] + dp[i][x][1]
            if x >= 1:
                dp[i+1][x][0] += dp[i][x-1][0]
                dp[i+1][x][1] += dp[i][x-1][0]*(num-1) + dp[i][x-1][1]*9
    


print(sum(dp[len(N)][K]))

Solution (Python):

import sys

sysread = sys.stdin.readline
read = sys.stdin.read


sys.setrecursionlimit(10**7)
import math
from itertools import combinations, product


def run():
    N,K = read().split()

    N = list(map(int,N))
    K = int(K)
    max_i = len(N)
    dp2 = [0] * max_i
    r = 0
    for i, v in enumerate(N):
        if v != 0:
            r += 1
        dp2[i] = r

    dp1 = [[0] * (K+1) for _ in range(max_i)]

    dp1[0][1] = int(N[0]-1)
    dp1[0][0] = 1
    for i in range(1, max_i):
        for j in range(0, K+1):
            if j == 0:
                dp1[i][j] += dp1[i - 1][j]
            else:
                dp1[i][j] += dp1[i - 1][j] + dp1[i - 1][j - 1] * 9
        if N[i] == 0:continue
        if dp2[i-1] <= K:
            dp1[i][dp2[i-1]] += 1
        if dp2[i-1] < K:
            dp1[i][dp2[i-1]+1] += N[i] - 1
    plus = 0
    if dp2[-1] == K:
        plus = 1
    print(dp1[max_i-1][K] + plus)




if __name__ == "__main__":
    run()

Solution (Python):
N_string = input()
l = len(N_string)
N = int(N_string)
K = int(input())

n = int(N_string[0])
dp0 = [[n - 1, 0, 0]]
dp1 = [[1, 0, 0]]

for i in range(l - 1):
    n = int(N_string[i + 1])
    if n == 0:
        dp0.append([9 + dp0[i][0],
                    dp0[i][0] * 9 + dp0[i][1],
                    dp0[i][1] * 9 + dp0[i][2]])
        dp1.append([dp1[i][0], dp1[i][1], dp1[i][2]])
    else:
        dp0.append([9 + dp0[i][0] + dp1[i][0],
                    dp0[i][0] * 9 + dp0[i][1] + dp1[i][0] * (n - 1) + dp1[i][1],
                    dp0[i][1] * 9 + dp0[i][2] + dp1[i][1] * (n - 1) + dp1[i][2]])
        dp1.append([0, dp1[i][0], dp1[i][1]])
print(dp0[-1][K - 1] + dp1[-1][K - 1])

Solution (Python):

import sys

sysread = sys.stdin.readline
read = sys.stdin.read


sys.setrecursionlimit(10**7)
import math
from itertools import combinations, product


def run():
    N,K = map(int, read().split())
    k = int(math.log(N, 10))
    s = N // (10 ** k)

    tmp1, tmp2, div = 1, 1, 1
    for i in range(K-1):
        tmp1 *= k-i
        div *= i+1
        tmp2 *= 9
    ret = tmp1//div * tmp2
    ret *= s-1

    tmp1 *= k - (K-1)
    tmp2 *= 9
    div *= K

    ret += tmp1 * tmp2 // div
    lis = range(k)
    nums = range(1,10)
    base = s * 10 ** k

    for A in combinations(lis, K-1):
        for X in product(nums, repeat = K-1):
            tmp = base
            for a,x in zip(A,X):
                tmp += 10 ** a * x
            if tmp <= N:
                ret += 1
    print(ret)



if __name__ == "__main__":
    run()

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

digit = len(str(n))

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

for a in range(1, digit + 1):
    digitvalue = int(str(n)[a - 1])
    for b in range(2):
        for c in range(k + 1):
            for d in range(10 if b == 1 else digitvalue + 1):
                dp[a][1 if b == 1 else 1 if (d < digitvalue) else 0][c if d == 0 else c + 1] += dp[a - 1][b][c]

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

Solution (Python):


def combination(n, r):
    
    if n < 0 or r < 0 or n < r:
        return 0

    
    if n - r < r:
        r = n - r

    
    if r == 0:
        return 1
    if r == 1:
        return n

    
    
    numerator = [n - r + 1 + i for i in range(r)]


    
    
    denominator = [i + 1 for i in range(r)]

    
    for i in range(r):
        
        

        
        original_denominator = i + 1

        
        
        divisor = denominator[i]

        
        if divisor == 1:
            continue

        
        
        
        
        
        
        
        
        
        
        

        
        
        
        remainder = (n - r) % original_denominator

        
        for j in range(i, r, original_denominator):
            numerator[j - remainder] = numerator[j - remainder] // divisor
            denominator[j] = denominator[j] // divisor

    ans = 1
    for i in numerator:
        ans *= i
    return ans


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

if N < 10:
    if K == 1:
        print(N)
    else:
        print(0)







else:
    
    
    n = len(N_string) - 1

    
    ans = combination(n, K) * (9 ** K)

    
    a = int(N_string[0])

    if K == 1:
        ans += a
    else:
        
        if N_string[1:] == "0" * n:
            
            ans += (a - 1) * combination(n, K - 1) * (9 ** (K - 1))
        else:
            
            
            m = n - 1
            while True:
                if N_string[n - m] != "0":
                    b = int(N_string[n - m])
                    break
                m -= 1

            if K == 2:
                
                
                ans += (a - 1) * combination(n, K - 1) * 9

                
                
                ans += combination(m, 1) * 9 + b
            else:
                
                
                if N_string[n - m + 1:] == "0" * m:
                    

                    
                    
                    ans += (a - 1) * combination(n, 2) * 9 * 9

                    
                    
                    ans += combination(m, 2) * 9 * 9

                    
                    
                    
                    ans += (b - 1) * combination(m, 1) * 9
                else:
                    
                    l = m - 1
                    while True:
                        if N_string[n - l] != "0":
                            c = int(N_string[n - l])
                            break
                        l -= 1

                    
                    
                    ans += (a - 1) * combination(n, K - 1) * 9 * 9

                    
                    
                    ans += combination(m, K - 1) * 9 * 9

                    
                    
                    
                    ans += (b - 1) * combination(m, K - 2) * 9

                    
                    
                    
                    ans += combination(l, 1) * 9 + c

    print(ans)

Solution (Python):
N = list(map(int,list(input())))
K = int(input())
L = len(N)
dp1 = [[0 for i in range(K+1)] for j in range(L+1)]
dp2 = [[0 for i in range(K+1)] for j in range(L+1)]
dp1[0][0] = 1

for i in range(L):
    for j in range(K+1):
        if N[i] == 0:
            dp1[i+1][j] += dp1[i][j]
        else:
            dp2[i+1][j] += dp1[i][j]
            if j > 0:
                dp1[i+1][j] += dp1[i][j-1]
                dp2[i+1][j] += dp1[i][j-1] * (N[i] - 1)
        if j > 0:
            dp2[i+1][j] += dp2[i][j-1] * 9
        dp2[i+1][j] += dp2[i][j]

ans = dp1[L][K] + dp2[L][K]

print(ans)

Solution (Python):
N = int(input())
n = str(N)
ln = len(n)
K = int(input())
dp0= [[0] * (K+2) for i in range(ln+1)]

dp1 = [[0] * (K+2) for i in range(ln+1)]


dp1[0][0] = 1

for i in range(ln):
  x = int(n[i])
  dp0[i+1][0] = 1
  for j in range(K):
    if(x == 0):
      dp0[i+1][j+1] = 9*dp0[i][j]+dp0[i][j+1]
      dp1[i+1][j+1] = dp1[i][j+1]
    else:
      dp0[i+1][j+1] = 9*dp0[i][j]+dp0[i][j+1]+(x-1)*dp1[i][j]+dp1[i][j+1]
      dp1[i+1][j+1] = dp1[i][j]
  
  
print(dp0[ln][K]+dp1[ln][K])

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

digit = len(str(n))

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

dp[0][1][0] = 1
for a in range(1, digit + 1):
    digitvalue = int(str(n)[a - 1])
    for c in range(k + 1):
        if c == k:
            
            dp[a][0][c] += dp[a-1][0][k] * 1
            dp[a][0][c] += dp[a-1][0][k-1] * 9
            
            
            dp[a][0][c] += dp[a-1][1][k] * (1 if digitvalue != 0 else 0)
            
            
            dp[a][0][c] += dp[a-1][1][k-1] * (digitvalue - 1 if digitvalue != 0 else 0)
            
            dp[a][1][c] += dp[a-1][1][k] * (1 if digitvalue == 0 else 0)
            dp[a][1][c] += dp[a-1][1][k-1] * (1 if digitvalue != 0 else 0)
        elif c != k:
            
            dp[a][0][c] += dp[a-1][0][c] * 1
            dp[a][0][c] += 0 if c == 0 else dp[a-1][0][c-1] * 9
            dp[a][0][c] += dp[a-1][1][c] * (1 if digitvalue != 0 else 0)
            dp[a][0][c] += 0 if c == 0 else dp[a-1][1][c-1] * (digitvalue - 1 if digitvalue != 0 else 0)
            dp[a][1][c] += dp[a - 1][1][c] * (1 if digitvalue == 0 else 0)
            dp[a][1][c] += 0 if c == 0 else dp[a - 1][1][c - 1] * (1 if digitvalue != 0 else 0)
        else:
            None






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

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

keta = len(str(n))

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

dp[0][1][0] = 1
for a in range(1, keta + 1):
    digit = int(str(n)[a - 1])
    for b in range(2):
        for c in range(k + 1):
            if b == 0 and c == k:
                
                dp[a][b][c] += dp[a-1][0][k] * 1
                dp[a][b][c] += dp[a-1][0][k-1] * 9
                
                
                dp[a][b][c] += dp[a-1][1][k] * (1 if digit != 0 else 0)
                
                
                dp[a][b][c] += dp[a-1][1][k-1] * (digit - 1 if digit != 0 else 0)
            elif b == 0 and c != k:
                
                dp[a][b][c] += dp[a-1][0][c] * 1
                dp[a][b][c] += 0 if c == 0 else dp[a-1][0][c-1] * 9
                dp[a][b][c] += dp[a-1][1][c] * (1 if digit != 0 else 0)
                dp[a][b][c] += 0 if c == 0 else dp[a-1][1][c-1] * (digit - 1 if digit != 0 else 0)
            elif b == 1 and c == k:
                
                dp[a][b][c] += dp[a-1][1][k] * (1 if digit == 0 else 0)
                dp[a][b][c] += dp[a-1][1][k-1] * (1 if digit != 0 else 0)
            elif b == 1 and c != k:
                dp[a][b][c] += dp[a-1][1][c] * (1 if digit == 0 else 0)
                dp[a][b][c] += 0 if c == 0 else dp[a-1][1][c-1] * (1 if digit != 0 else 0)
            else:
                None






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

Solution (Python):
def case_k1(n):
    digit = len(str(n))
    if digit ==1:
        return n
    else:
        return (n//(10**(digit-1))+(digit-1)*9)

def case_k2(n):
    digit = len(str(n))
    if digit == 1:
        return 0
    elif digit ==2:
        return (n//10-1)*9+n%10
    else:
        sum = 0
        for i in range(1,digit-1):
            sum += i*81
        q = n//(10**(digit-1))
        r = n-q*10**(digit-1)
        r_digit = len(str(r))
        sum += (q-1)*(case_k1(10**(digit-1)-1)) + case_k1(r)
        return sum

def case_k3(n):
    digit = len(str(n))
    if digit <3:
        return 0
    else:
        sum = 0
        for i in range(2,digit-1):
            sum += 9*case_k2(10**(i)-1)
        q = n//(10**(digit-1))
        r = n-q*10**(digit-1)
        sum += (q-1)*(case_k2(10**(digit-1)-1)) + case_k2(r)
        return sum

N = input()
K = int(input())
n = int(N)
if K ==1:
    print(case_k1(n))
elif K ==2:
    print(case_k2(n))
else:
    print(case_k3(n))

Solution (Python):
n = int(input())
k = int(input())
len_n = len(str(n))
dp = [[[0] * (k + 1) for i in range(2)] for j in range(len_n + 1)]
dp[0][0][0] = 1

for i in range(1, len_n + 1):
    l = int(str(n)[i - 1])
    for m in range(k + 1):
        dp[i][1][m] += dp[i - 1][1][m]
        if l != 0:
            dp[i][1][m] += dp[i - 1][0][m]
        else:
            dp[i][0][m] += dp[i - 1][0][m]
        if m - 1 >= 0:
            dp[i][1][m] += 9 * dp[i - 1][1][m - 1]
            if l != 0:
                dp[i][0][m] += dp[i - 1][0][m - 1]
                dp[i][1][m] += (l - 1) * dp[i - 1][0][m - 1]

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

Solution (Python):
from functools import lru_cache
from sys import setrecursionlimit
setrecursionlimit(10000)
N = input()
K = int(input())

@lru_cache()
def f(n, k):
    if k == 0:
        return 1
    if len(n) == 1:
        if k == 1:
            return int(n)
        else:
            return 0
    m = int(n[-1])
    return f(n[:-1], k) + f(n[:-1], k - 1) * m + f(str(int(n[:-1]) - 1), k - 1) * (9 - m)

print(f(N, K))

Solution (Python):
def nCk(n,k):
    res = 1
    for i in range(k,0,-1):
        res = res*(n+1-i)/i
    return int(res)

N = input()
K = int(input())
ans = 0
dp_mikakutei = [[0 for i in range(0,K+1,1)] for j in range(0,len(N),1)]
dp_kakutei = [[0 for i in range(0,K+1,1)] for j in range(0,len(N),1)]

dp_mikakutei[0][1]=1
dp_kakutei[0][0]=1
dp_kakutei[0][1]=int(N[0])-1

for i in range(1,len(N),1):
    dp_kakutei[i][0]=dp_kakutei[i-1][0] + dp_mikakutei[i-1][0]
    for j in range(1,K+1,1):
        if N[i] =="0":
            dp_mikakutei[i][j] = dp_mikakutei[i-1][j]
            dp_kakutei[i][j] = 9*dp_kakutei[i-1][j-1] +dp_kakutei[i-1][j]
        else:
            dp_mikakutei[i][j] = dp_mikakutei[i-1][j-1]
            dp_kakutei[i][j] = 9*dp_kakutei[i-1][j-1] + (int(N[i])-1)*dp_mikakutei[i-1][j-1] + dp_kakutei[i-1][j] + dp_mikakutei[i-1][j]
print(dp_mikakutei[len(N)-1][K] + dp_kakutei[len(N)-1][K])

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


def func_1(N):
    Nm = int(N[0])
    return Nm + 9 * (len(N) - 1)


def func_2(N):
    
    

    Nm = int(N[0])
    m = len(N)
    
     
    
    
    x = int(N) - Nm * pow(10, m-1)
    
    
    


    return  int((Nm-1)*(m-1)*9+(m-1)*(m-2)*9*9/2+func_1(str(x)))

def func_3(N):
    
    Nm = int(N[0])
    m = len(N)
   
     
    return int(pow(9,3)*(m-1)*(m-2)*(m-3)/6+(Nm-1)*(m-1)*(m-2)*9*9/2+func_2(str(int(N)-Nm*(10**(m-1)))))



if K == 1:
    print(func_1(N))
elif K == 2:
    print(func_2(N))
elif K == 3:
    print(func_3(N))

Solution (Python):


import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))

def resolve():
    N=input()
    K,=pin()

    
    
    
    rb=(0,1)
    dp_table=[[[0 for cnd in range(K+1)]for sml in rb]for ind in range(len(N)+1)]
    dp_table[0][0][0]=1
    
    
    for degit in range(len(N)+1):
        n=int(N[degit-1])
        for sml in rb:
            t=10 if sml else int(N[degit-1])+1
            for k in range(K+1):
                for prove in range(t):
                    x=prove
                    try:
                        
                        
                        dp_table[degit][sml or x<n][k+(x!=0)]+=dp_table[degit-1][sml][k]
                    except :pass

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

resolve()

Solution (Python):
import sys
import math
sys.setrecursionlimit(1000000)


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

from functools import lru_cache

@lru_cache(maxsize=10000)
def f(n,k):
    
    if k == 0:
        return 1
    if k== 1 and n < 10:
        return n

    keta = len(str(n))
    if keta < k:
        return 0

    h = n // (10 ** (keta-1))
    b = n % (10 ** (keta-1))

    ret = 0
    for i in range(h+1):
        if i==0:
            ret += f(10 ** (keta-1) - 1, k)
        elif 1 <= i < h:
            ret += f(10 ** (keta-1) - 1, k-1)
        else:
            ret += f(b,k-1)
        
    return ret

print(f(N,K))

Solution (Python):
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K+1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1

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

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

Solution (Python):
s=input()
n=len(s)
K=int(input())
dp=[[[0,0] for _ in range(K+1)] for _ in range(n+1)]
dp[0][0][0]=1
r=range
for i in r(n):
  nd=int(s[i])
  for j in r(K+1):
    for k in r(2):
      for d in r(10):
        ni,nj,nk=i+1,j,k
        if d: nj+=1
        if nj>K: continue
        if k<1:
          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):
def f(n,k):
  if k<1: return 1
  if n<10:
    if k<2: return n
    return 0
  d,m=n//10,n%10
  return f(d,k-1)*m+f(d-1,k-1)*(9-m)+f(d,k)
print(f(int(input()),int(input())))

Solution (Python):
from functools import lru_cache
@lru_cache(None)
def f(n,k):
  if k<1: return 1
  if n<10:
    if k<2: return n
    return 0
  d,m=n//10,n%10
  return f(d,k-1)*m+f(d-1,k-1)*(9-m)+f(d,k)
print(f(int(input()),int(input())))

Solution (Python):
from functools import lru_cache
@lru_cache(None)
def f(n,k):
  if n<10:
    if k<1: return 1
    if k<2: return n
    return 0
  d,m=divmod(n,10)
  c=0
  if k:
    c+=f(d,k-1)*m
    c+=f(d-1,k-1)*(9-m)
  c+=f(d,k)
  return c
print(f(int(input()),int(input())))

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

Solution (Python):
import math

N = int(input())
K = int(input())
l = len(str(N))

dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(102)]
dp[0][0][0] = 1

for i in range(l):
    for j in range(4):
        for k in range(2):
            for d in range(10):
                nd = int(str(N)[i])
                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):
N=int(input())
K=int(input())
s=str(N)
N=len(s)



dp=[[[0]*(K+2) for j in range(2)] for i in range(N+1)]
dp[0][0][0]=1
for i in range(N):
  for k in range(K+1):
    ni=int(s[i])
    
    dp[i+1][1][k+1]+=dp[i][1][k]*9 
    dp[i+1][1][k]+=dp[i][1][k]     
    
    if ni>0:
      dp[i+1][1][k+1]+=dp[i][0][k]*(ni-1) 
      dp[i+1][1][k]+=dp[i][0][k]          
    
    if ni>0:
      dp[i+1][0][k+1]=dp[i][0][k] 
    else:
      dp[i+1][0][k]=dp[i][0][k]   
print(dp[N][0][K]+dp[N][1][K])

Solution (Python):
s = input()
K = int(input())
n = len(s)

dp = [[[0]*5 for _ in range(2)] for _ in range(10001)]
dp[0][0][0] = 1

for i in range(n):
  for k in range(K+1):
    x = int(s[i])
    
    dp[i+1][1][k+1] += dp[i][1][k] * 9
    dp[i+1][1][k]   += dp[i][1][k]        
    
    if x > 0:
      dp[i+1][1][k+1] += dp[i][0][k] * (x-1)
      dp[i+1][1][k]   += dp[i][0][k]
      dp[i+1][0][k+1] = dp[i][0][k]
    else:
      dp[i+1][0][k] = dp[i][0][k]
      
print( dp[n][0][k]+ dp[n][1][k])

Solution (Python):
n=input()
K=int(input())
m=len(n)

DP=[[[0]*(K+2) for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(K+1):
            for k in range(num+1):
                if k==0:DP[i][flag or k<num][j] +=DP[i-1][flag][j]
                else:DP[i][flag or k<num][j+1] +=DP[i-1][flag][j]

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

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

OK=[[0 for k in range(5)]for i in range(len(N))]
OK[0][0]=1
OK[0][1]=int(N[0])-1
D=1

for i in range(1,len(N)):
    OK[i][0]=OK[i-1][0]
    OK[i][1]+=OK[i-1][0]*9+OK[i-1][1]
    OK[i][2]+=OK[i-1][1]*9+OK[i-1][2]
    OK[i][3]+=OK[i-1][2]*9+OK[i-1][3]
    if D<=K and int(N[i])!=0:
        OK[i][D]+=1
        OK[i][D+1]+=int(N[i])-1
        D+=1
if D==K:
    print(OK[-1][K]+1)
else:
    print(OK[-1][K])

Solution (Python):
n = input()
k = int(input())
ans = 0
for i in range(1,len(n)):
    if (i < k):
        continue
    else:
        if (k==1):
            ans += 9
        elif (k==2):
            ans += 9*(i-1)*9
        else:
            ans += 9*9*9*(i-1)*(i-2)//2
    
if (k==1):
    ans += int(n[0])
elif (k==2):
    ans += (int(n[0])-1)*(len(n)-1)*9
    
    for i in range(1,len(n)):
        if (int(n[i])>0):
            ans += 9*(len(n)-i-1)
            ans += int(n[i])
            break
        if (i==len(n)-1):
            print(ans)
            exit()
else:
    ans += (int(n[0])-1)*9*9*(len(n)-1)*(len(n)-2)//2
    for i in range(1,len(n)):
        if (int(n[i])>0):
            ans += (int(n[i])-1)*9*(len(n)-i-1)
            ans += 9*9*(len(n)-i-1)*(len(n)-i-2)//2
            t = i
            break
        if (i==len(n)-2):
            print(ans)
            exit()
    for j in range(t+1,len(n)):
        if (int(n[j])>0):
            ans += int(n[j])
            ans += 9*(len(n)-j-1)
            break
print(ans)

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

dp = [[[0 for _ in range(5)] for _ in range(2)] for _ in range(N+5)]
dp[1][0][1] = 1
dp[1][1][0] = 1
dp[1][1][1] = int(S[0])-1

for i in range(1, N):
    n = int(S[i])
    ok = 0 if n == 0 else 1
    for j in range(4):
        dp[i+1][0][j+ok] += dp[i][0][j]
        if n > 0:
            dp[i+1][1][j] += dp[i][0][j]
            dp[i+1][1][j+1] += (n-1)*dp[i][0][j]
        dp[i+1][1][j] += dp[i][1][j]
        dp[i+1][1][j+1] += 9*dp[i][1][j]

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

Solution (Python):




N=str(input())
K=int(input())
L=len(N)


DP=[[[0]*5 for index1 in range(2)] for index2 in range(L+1)]

DP[0][0][0]=1



for i in range(1,L+1):
    
    DP[i][1][4]+=DP[i-1][1][4]*10+DP[i-1][1][3]*9
    DP[i][1][3]+=DP[i-1][1][3]+DP[i-1][1][2]*9
    DP[i][1][2]+=DP[i-1][1][2]+DP[i-1][1][1]*9
    DP[i][1][1]+=DP[i-1][1][1]+DP[i-1][1][0]*9
    DP[i][1][0]+=DP[i-1][1][0]

    n=int(N[i-1])

    
    
    
    if n==1:
        DP[i][1][4]+=DP[i-1][0][4]
        DP[i][1][3]+=DP[i-1][0][3]
        DP[i][1][2]+=DP[i-1][0][2]
        DP[i][1][1]+=DP[i-1][0][1]
        DP[i][1][0]+=DP[i-1][0][0]
    elif n>=2:
        DP[i][1][4]+=DP[i-1][0][4]*n+DP[i-1][0][3]*(n-1)
        DP[i][1][3]+=DP[i-1][0][3]+DP[i-1][0][2]*(n-1)
        DP[i][1][2]+=DP[i-1][0][2]+DP[i-1][0][1]*(n-1)
        DP[i][1][1]+=DP[i-1][0][1]+DP[i-1][0][0]*(n-1)
        DP[i][1][0]+=DP[i-1][0][0]

    
    
    if n==0:
        DP[i][0][4]+=DP[i-1][0][4]
        DP[i][0][3]+=DP[i-1][0][3]
        DP[i][0][2]+=DP[i-1][0][2]
        DP[i][0][1]+=DP[i-1][0][1]
        DP[i][0][0]+=DP[i-1][0][0]
    else:
        DP[i][0][4]+=DP[i-1][0][4]+DP[i-1][0][3]
        DP[i][0][3]+=DP[i-1][0][2]
        DP[i][0][2]+=DP[i-1][0][1]
        DP[i][0][1]+=DP[i-1][0][0]

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    

    n = input().rstrip()
    k = int(input())
    ln = len(n)
    
    dp1 = [[0]*(k+1) for _ in range(ln+1)]
    dp2 = [[0]*(k+1) for _ in range(ln+1)]

    dp2[0][0] = 1
    cnt = 0
    for i in range(ln):
        if n[i] != '0':
            if cnt < k:
                cnt += 1
            dp2[i+1][cnt] = 1
        else:
            dp2[i+1][cnt] = dp2[i][cnt]

    for i in range(ln):
        dp1[i+1][0] = 1
        for j in range(1, k+1):
            dp1[i+1][j] += dp1[i][j] + dp1[i][j-1] * 9
            if n[i] != '0':
                dp1[i+1][j] += dp2[i][j-1] * (int(n[i])-1)
                if j < k:
                    dp1[i+1][j] += dp2[i][j]
    print(dp1[-1][k] + dp2[-1][k])

if __name__ == '__main__':
    main()

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



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

for i in range(len(n)):
    nd = int(n[i])
    for j in [0, 1]:
        for l in range(k+1):
            for d in range(10):
                ni=i+1
                nj=j
                nl=l

                if d!=0:
                    nl+=1
                if nl>k:
                    continue
                if j==0: 
                    if d > nd:
                        continue
                    if d < nd:
                        nj=1 
                dp[ni][nj][nl] += dp[i][j][l]

print(dp[len(n)][0][k]+dp[len(n)][1][k])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    mod = 10**9 + 7
    def ncr(n, r, mod):
        r = min(r, n-r)
        numer = denom = 1
        for i in range(1, r+1):
            numer = numer * (n+1-i) % mod
            denom = denom * i % mod
        return numer * pow(denom, mod-2, mod) % mod

    n = input().rstrip()
    k = int(input())
    ln = len(n)
    if ln < k:
        print(0)
        exit()
    res = 0
    if k == 1:
        if ln >= 2:
            res += ncr(ln-1, 1, mod) * 9
        res += int(n[0])
    if k == 2:
        if ln >= 3:
            res += ncr(ln-1, 2, mod) * (9**k)
        res += ncr(ln-1, 1, mod) * 9 * (int(n[0])-1)
        for i in range(1, ln):
            if n[i] != '0':
                if i == ln-1:
                    res += int(n[i])
                else:
                    res += ncr(ln-i-1, 1, mod) * 9
                    res += int(n[i])
                break
    if k == 3:
        if ln >= 4:
            res += ncr(ln-1, 3, mod) * (9**k)
        res += ncr(ln-1, 2, mod) * 81 * (int(n[0])-1)
        for i in range(1, ln-1):
            if n[i] != '0':
                if ln-i-1 >= 2:
                    res += ncr(ln-i-1, 2, mod) * 81
                res += ncr(ln-i-1, 1, mod) * 9 * (int(n[i])-1)
                for j in range(i+1, ln):
                    if n[j] != '0':
                        if j != ln-1:
                            res += ncr(ln-j-1, 1, mod) * 9 
                        res += int(n[j])
                        break
                break
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
N=input()
cnt=int(input())
L=len(N)
dp=[[[0]*(cnt+1) for j in range(2)] for i in range(L+1)]
dp[0][0][0]=1
for i in range(L):
    for j in range(2):
        for k in range(cnt+1):
            D=int(N[i])
            for d in range(10 if j else D+1):
                K=k+int(d!=0)
                if K>cnt:
                    continue
                dp[i+1][int(j or d<D)][K]+=dp[i][j][k]
print(dp[-1][0][-1]+dp[-1][1][-1])

Solution (Python):
S = list(map(int,list(input())))
K = int(input())
from itertools import groupby, accumulate, product, permutations, combinations
def solve(S,K):
    ans = 0
    n = len(S)
    dp1 = [[0]*5 for _ in range(n)]
    dp0 = [[0]*5 for _ in range(n)]
    dp0[0][1] = 1
    dp1[0][0] = 1
    dp1[0][1] = S[0]-1
    for i in range(1,n):
        for j in range(4):
            dp1[i][j] = dp1[i-1][j]+dp1[i-1][j-1]*9
            if S[i]==0:
                dp0[i][j] = dp0[i-1][j]
            else:
                dp0[i][j] = dp0[i-1][j-1]
                dp1[i][j] += dp0[i-1][j-1]*(S[i]-1)+dp0[i-1][j]
    ans = dp1[n-1][K]+dp0[n-1][K]
    return ans
print(solve(S,K))

Solution (Python):
n=input()
k=int(input())
dp=[[[0]*(k+2) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0]=1
for i,c in enumerate(n):
  c=int(c)
  for j in range(2):
    for l in range(k+1):
      for nxt in range(10*j or c+1):
        dp[i+1][j or nxt<c][l+(nxt>0)]+=dp[i][j][l]
print(dp[-1][1][k]+dp[-1][0][k])