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):


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

    ans = 0
    
    
    if K == 1:
        ans += (l-1) * 9
    elif K == 2:
        ans += (l-1) * (l-2) * 81 // 2
    else:
        ans += (l-1) * (l-2) * (l-3) * 729 // 6

    if K == 1:
        
        ans += int(N[0])
    elif K == 2:
        
        if l >= 2:
            
            for a in range(1,int(N[0])+1):
                for b in range(l-1):
                    for p in range(1,10):
                        tmp = a * 10**(l-1) + p * 10**b
                        if tmp <= int(N):
                            ans += 1
    else:
        
        if l >= 3:
            NN = int(N)
            N0 = int(N[0])
            L = 10**(l-1)

            ans += (N0-1) * (l-1) * (l-2) * 81 // 2

            for p in range(1,10):
                for q in range(1,10):
                    for b in range(l-1):
                        for c in range(b+1,l-1):
                            tmp = N0 * L + p * 10**b + q * 10**c
                            if tmp <= NN:
                                ans += 1
                            else:
                                break
    print(ans)

if __name__ == "__main__":
    main()

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

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

dp1=[0]*(k+1)
dp2=[0]*(k+1)
dp1[0]=1

for x in map(int,str(n)):
    for j in range(k,-1,-1):
        if j>0:
            dp2[j]+=dp2[j-1]*9
            if x!=0:
                dp2[j]+=dp1[j-1]*(x-1)+dp1[j]
                dp1[j]=dp1[j-1]
            
            
        else:
            dp2[j]=1
            dp1[j]=0
print(dp1[k]+dp2[k])

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

if len(N) < K:
  print(0)
  exit()

ans = [1, int(N[-1]), 0, 0];
nine = [1, 9, 81, 729]

def combination(N,K):
  if N < K:
    return 0
  elif K == 0:
    return 1
  elif K == 1:
    return N
  elif K == 2:
    return N*(N-1)//2
  else:
    return N*(N-1)*(N-2)//6

for k in range(1, len(N)):
  if int(N[-k-1]) > 0:
    a = [1, 0, 0, 0]
    for j in range(1, K+1):
      a[j] += nine[j]*combination(k, j)
      a[j] += (int(N[-k-1])-1)*combination(k, j-1)*nine[j-1] + ans[j-1]
    ans = a
print(ans[K])

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

if len(N) < K:
  print(0)
  exit()

ans = [1, int(N[-1]), 0, 0];

def combination(N,K):
  if N < K:
    return 0
  else:
    p = 1
    for k in range(K):
      p *= N
      N -= 1
    for k in range(1, K+1):
      p //= k
    return p

for k in range(1, len(N)):
  if int(N[-k-1]) > 0:
    a = [1, 0, 0, 0]
    for j in range(1, K+1):
      a[j] += (9**(j))*combination(k, j)
      a[j] += (int(N[-k-1])-1)*combination(k, j-1)*(9**(j-1)) + ans[j-1]
    ans = a
print(ans[K])

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

if len(N) < K:
  print(0)
  exit()

keta = []
for k in range(len(N)):
  keta.append(int(N[-k-1]))
ans = [1, keta[0], 0, 0];

def combination(N,K):
  if N < K:
    return 0
  else:
    p = 1
    for k in range(K):
      p *= N
      N -= 1
    for k in range(1, K+1):
      p //= k
    return p
for k in range(1, len(N)-1):
  if keta[k] > 0:
    a = [1, 0, 0, 0]
    for j in range(1, 4):
      a[j] += (9**(j))*combination(k, j)
      a[j] += (keta[k]-1)*combination(k, j-1)*(9**(j-1)) + ans[j-1]
    ans = [] + a
answer = (9**(K))*combination(len(N)-1, K)
answer += (keta[-1]-1)*(9**(K-1))*combination(len(N)-1, K-1)
answer += ans[K-1]
print(answer)

Solution (Python):



def digit(N, M):
    """
    :param N: 0 <= n <= N の整数 (※ 下限が 1 の場合は返り値を -= 1 等する)
    :param M: 状態数（例: 0<= (0の個数) <= M）

    dp[0][i][*]: 上からi桁目までが N と一致
    dp[1][i][*]: 上からi桁目までで N である事が確定
    dp[*][*][j]: 状態 j の個数（今回は j = (0 の個数) ）
    """
    def f(j,k):
        """状態 j からの繊維。 i+1 桁目の数( = j)に依存"""
        return min2(j + (k != 0), M - 1)

    L = len(N)
    dp = [[[0] * M for i in range(L + 1)] for j in range(2)]

    dp[0][0][0] = 1
    for i in range(L):
        for j in range(M):
            for k in range(10):
                if k < N[i]:
                    dp[1][i+1][f(j, k)] += dp[0][i][j] + dp[1][i][j]
                elif k == N[i]:
                    dp[0][i+1][f(j, k)] += dp[0][i][j]
                    dp[1][i+1][f(j, k)] += dp[1][i][j]
                else:
                    dp[1][i+1][f(j, k)] += dp[1][i][j]

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



N = list(map(int, input().strip()))     
K = int(input())
M = K + 2                               

def min2(x,y):
    return x if x < y else y

print(digit(N, M))

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

def min2(x,y):
    return x if x < y else y

"""
dp[0][i][*]: 上からi桁目までが N と一致
dp[1][i][*]: 上からi桁目までで N である事が確定
dp[*][*][j]: 0 でない数字の個数が j 個
"""
dp[0][0][0] = 1
for i in range(L):
    for j in range(D):
        for k in range(10):
            if k < N[i]:
                dp[1][i+1][min2(j + (k!=0), D-1)] += dp[0][i][j] + dp[1][i][j]
            elif k == N[i]:
                dp[0][i+1][min2(j + (k!=0), D-1)] += dp[0][i][j]
                dp[1][i+1][min2(j + (k!=0), D-1)] += dp[1][i][j]
            else:
                dp[1][i+1][min2(j + (k!=0), D-1)] += dp[1][i][j]

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

Solution (Python):
from sys import stdin,stdout
def fn(pos,res,k):
    if pos==n:return (k==0)
    ans=0
    if (pos,res,k) in dp:return dp[pos,res,k]
    cur=ord(s[pos])-48
    if res:
        for d in range(cur+1):
            if d==0:ans+=fn(pos+1,d==cur,k)
            elif d!=0 and k>0:ans+=fn(pos+1,d==cur,k-1)
    else:
        for d in range(10):
            if d == 0:ans += fn(pos + 1,0, k)
            elif d != 0 and k > 0:ans += fn(pos + 1,0, k - 1)
    dp[pos,res,k]=ans
    return ans


s=input()
n=len(s)
k1=int(stdin.readline())
dp={}
ans=0
for d in range(10):
    if d+48<=ord(s[0]):
        ans+=fn(1,(d==ord(s[0])-48),(k1-(d!=0)))
print(ans)

Solution (Python):
def main():
    n = input()
    non_zero = int(input())
    length = len(n)
    dp = [[[0, 0] for _ in range(non_zero + 1)] for _ in range(length + 1)]
    dp[0][0][0] = 1
    for i in range(length):
        for j in range(non_zero + 1):
            for k in range(2):
                now_digit = int(n[i])
                for next_d in range(10):
                    new_i = i + 1
                    new_j = j
                    new_k = k
                    if next_d > 0:
                        new_j += 1
                    if new_j > non_zero:
                        continue
                    if k == 0:
                        if next_d > now_digit:
                            continue
                        elif next_d < now_digit:
                            new_k = 1
                    dp[new_i][new_j][new_k] += dp[i][j][k]
    print(sum(dp[length][non_zero]))


if __name__ == '__main__':
    main()

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



dp0 = [[0 for _ in range(5)] for _ in range(L+1)]
dp1 = [[0 for _ in range(5)] for _ in range(L+1)]
dp0[0][0] = 1
dp0[0][1] = 0
for i in range(L):
    D = int(S[i])
    for j in range(4):
        if D > 0:
            
            dp1[i+1][j] += dp1[i][j] + dp0[i][j]
            
            dp0[i+1][j+1] += dp0[i][j]
            dp1[i+1][j+1] += dp1[i][j]*9 + dp0[i][j]*(D-1)
        else:
            
            dp0[i+1][j] += dp0[i][j]
            dp1[i+1][j] += dp1[i][j]
            
            dp1[i+1][j+1] += dp1[i][j]*9
print(dp0[L][K]+dp1[L][K])

Solution (Python):
n = input()
k = int(input())
ln = len(n) + 1

dp=[[[0]* (ln) for _ in range(2)] for i in range(ln)]
dp[0][0][0] = 1
for i in range(len(n)):
  for smaller in range(2):
    x = int(n[i])
    t = 9 if smaller else x
    for j in range(t+1):
      for knum in range(ln-1):
        if j == 0:
          dp[i+1][int(smaller or j < x)][knum] += dp[i][smaller][knum]
        else:
          dp[i+1][int(smaller or j < x)][knum+1] += dp[i][smaller][knum]
try:
  print(dp[-1][0][k] + dp[-1][1][k])
except:
  print(0)

Solution (Python):
def solve():
    s = [int(x) for x in input()]
    n = len(s)
    m = int(input())
    dp = [[[0] * 5 for _ in range(2)] for _ in range(n + 1)]
    dp[0][0][0] = 1

    for i in range(n):
        for k in range(m + 1):
            dp[i + 1][1][k + 1] += dp[i][1][k] * 9  
            dp[i + 1][1][k] += dp[i][1][k]  
            if s[i] > 0:
                dp[i + 1][1][k + 1] += dp[i][0][k] * (s[i] - 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][m] + dp[n][1][m])


solve()

Solution (Python):




from sys import setrecursionlimit

setrecursionlimit(10**7)

n = input()
k = int(input())
dp = {}


def rec(i, smaller, count):
    if (i, smaller, count) in dp:
        return dp[(i, smaller, count)]
    if i == len(n):
        if count == k:
            return 1
        else:
            return 0
    limit = 10
    if not smaller:
        limit = int(n[i]) + 1
    ret = 0
    for j in range(limit):
        if smaller or j < int(n[i]):
            if j == 0:
                ret += rec(i + 1, True, count)
            else:
                ret += rec(i + 1, True, count + 1)
        else:
            if j == 0:
                ret += rec(i + 1, False, count)
            else:
                ret += rec(i + 1, False, count + 1)
    dp[(i, smaller, count)] = ret
    return ret


print(rec(0, False, 0))

Solution (Python):
def f(N,K):
    n=len(str(N))
    if n==1:
        if K==1:
            return N
        else:
            return 0
    elif n==2:
        if K==1:
            return 9+N//10
        elif K==2:
            return N-9-N//10
        else:
            return 0
    elif n==3:
        if K==1:
            return 18+N//100
        elif K==2:
            return 81+18*((N//100)-1)+f(N%100,1)
        else:
            return 81*((N//100)-1)+f(N%100,2)
    else:
        if K==1:
            return 9*(n-1)+N//(10**(n-1))
        elif K==2:
            return 81*(n-1)*(n-2)/2+9*(n-1)*((N//((10**(n-1))))-1)+f(N%(10**(n-1)),1)
        else:
            return 243*(n**3-6*(n**2)+11*n-6)/2+81*(n-1)*(n-2)*((N//(10**(n-1)))-1)/2+f(N%(10**(n-1)),2)
N=int(input())
K=int(input())
print(int(f(N,K)))

Solution (Python):
from math import factorial
from itertools import product

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


product_K = product(['1', '2', '3', '4', '5', '6', '7', '8', '9'], repeat=K)
product_K = [int(''.join(x)) for x in product_K]
ans = len([x for x in product_K if x <= N])

if m > K:
    
    for i in range(1, m-K):
        ans += 9**K * factorial(i+K-1)//factorial(i)//factorial(K-1)
    
    
    zero_n = m-K
    non_zero_n = K
    for i in range(m):
        l = int(S[i])
        if l == 0:
            zero_n -= 1
            continue
        if i > 0 and zero_n > 0:
            ans += 9**non_zero_n\
                * factorial(zero_n-1 + non_zero_n)\
                //factorial(zero_n-1)\
                //factorial(non_zero_n)
        non_zero_n -= 1
        ans += len([x for x in range(1, l)])\
                * 9**non_zero_n\
                * factorial(zero_n + non_zero_n)\
                //factorial(zero_n)\
                //factorial(non_zero_n)
        
        if non_zero_n <= 0:
            ans += 1
            break
print(ans)

Solution (Python):

import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    list_N = list(map(int,list(input())))
    len_N = len(list_N)
    list_N = [0] + list_N

    K = II()
    dp0 = []
    dp1 = []
    for i in range(len_N+1):
        dp0.append([0]*(K+1))
        dp1.append([0]*(K+1))
    for i in range(1,len_N+1):
        dp0[i][0] = 1
    dp0[1][1] = max(list_N[1]-1,0)
    dp1[1][1] = 1
    for i in range(2,len_N+1):
        dp1[i][0] = dp1[i-1][0]
        for j in range(1,K+1):
            num = list_N[i]
            if num > 0:
                dp0[i][j] = dp0[i-1][j-1] * 9 + dp0[i-1][j] + dp1[i-1][j-1] * (num-1) + dp1[i-1][j]
                dp1[i][j] = dp1[i-1][j-1]
            else:
                dp0[i][j] = dp0[i-1][j-1] * 9 + dp0[i-1][j]
                dp1[i][j] = dp1[i-1][j]
                
    print(dp0[len_N][K]+dp1[len_N][K])
    dbg(dp0[len_N][K],dp1[len_N][K])






if __name__ == '__main__':
    main()

Solution (Python):
n=input()
K=int(input())
ns=len(n)
dp=[[[0]*(5) for _ in range(2)]for _ in range(ns+1)]
dp[0][0][0]=1
for i in range(ns):
    for k in range(K+1):
        dp[i+1][1][k+1]+=dp[i][1][k]*9
        dp[i+1][1][k]+=dp[i][1][k]
        if int(n[i])>0:
            dp[i+1][1][k+1]+=dp[i][0][k]*(int(n[i])-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[ns][0][K]+dp[ns][1][K])

Solution (Python):
from functools import lru_cache

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

@lru_cache(None)
def f(n, k):
  if k < 0:
    return 0
  if n < 10:
    if k == 0:
      return 1
    elif k == 1:
      return n
    else:
      return 0
  a, b = divmod(n, 10)
  return f(a, k) + f(a, k-1) * b + f(a-1, k-1) * (9-b)
  
print(f(N, K))

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


dp_small = [ [0]*5 for _ in range(keta+1)]
dp_same = [ [0]*5 for _ in range(keta+1)]

dp_small[0][0] = 0
dp_same[0][0] = 1

for i in range(keta):
    num = int(n[i])
    for j in range(4):
        dp_small[i+1][j+1] += dp_small[i][j] * 9
        dp_small[i+1][j] += dp_small[i][j]
        if num != 0:
            dp_small[i+1][j+1] += dp_same[i][j]*(num-1)
            dp_small[i+1][j] += dp_same[i][j]

        if num == 0:
            dp_same[i+1][j] += dp_same[i][j]
        else:
            dp_same[i+1][j+1] += dp_same[i][j]

print(dp_same[-1][k]+dp_small[-1][k])

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



S = input()
K = int(input())

import functools

@functools.lru_cache(None)
def rec(i, k, is_same):
    if k == 0:
        return 1
    if i == 0:
        if k >= 2:
            return 0
        if is_same == 1:
            return int(S[len(S) - i - 1])
        else:
            return 9

    res = 0
    a = int(S[len(S) - i - 1])
    if is_same == 1:
        for x in range(a + 1):
            if x == a and x == 0:
                res += rec(i - 1, k, 1)
            elif x == 0:
                res += rec(i - 1, k, 0)
            elif x == a:
                res += rec(i - 1, k - 1, 1)
            else:
                res += rec(i - 1, k - 1, 0)
    else:
        for x in range(10):
            if x == 0:
                res += rec(i - 1, k, 0)
            else:
                res += rec(i - 1, k - 1, 0)
    return res

n = len(S)
res = rec(n - 1, K, 1)
print(res)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



S = input()
K = int(input())

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

def rec(i, k, is_same):
    if dp[i][k][is_same] != 0:
        return dp[i][k][is_same]
    if k == 0:
        return 1
    if i == 0:
        if k >= 2:
            return 0
        if is_same == 1:
            dp[i][k][is_same] = int(S[len(S) - i - 1])
        else:
            dp[i][k][is_same] = 9
        return dp[i][k][is_same]

    res = 0
    a = int(S[len(S) - i - 1])
    if is_same == 1:
        for x in range(a + 1):
            if x == a and x == 0:
                res += rec(i - 1, k, 1)
            elif x == 0:
                res += rec(i - 1, k, 0)
            elif x == a:
                res += rec(i - 1, k - 1, 1)
            else:
                res += rec(i - 1, k - 1, 0)
    else:
        for x in range(10):
            if x == 0:
                res += rec(i - 1, k, 0)
            else:
                res += rec(i - 1, k - 1, 0)

    dp[i][k][is_same] = res
    return res

n = len(S)
res = rec(n - 1, K, 1)
print(res)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def solve():
    S = Scanner.string()
    N = len(S)
    K = Scanner.int()
    dp = [[[0 for _ in range(2)] for _ in range(K + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(4):
            for k in range(2):
                nd = int(S[i])
                for d in range(10):
                    ni, nj, nk = i + 1, j, 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])


def main():
    
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

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

dp=[[[0 for _ in range(4)] for _ in range(len(N))] for _ in range(2)]
for i in range(len(N)):
    num=N[i]
    mayover=0
    if i==0:
        id=0
        for j in range(10):
            if j==num:
                id=1
            elif j>num:
                break
            if j==0:
                dp[id][i][0]=dp[id][i][0]+1
            else:
                dp[id][i][1] = dp[id][i][1] + 1
    else:
        for j in range(2):
            for l in range(4):
                if j==0:
                    dp[j][i][l] = dp[j][i][l] + dp[j][i - 1][l]
                    if l != 0:
                        dp[j][i][l] = dp[j][i][l] + 9*dp[j][i - 1][l - 1]
                else:
                    if num==0:
                        for l in range(4):
                            dp[j][i][l] = dp[j][i - 1][l]
                    else:
                        dp[0][i][l] = dp[0][i][l] + dp[j][i - 1][l]
                        if l != 0:
                            dp[0][i][l] = dp[0][i][l] + (num - 1) * dp[j][i - 1][l - 1]
                            dp[1][i][l] = dp[1][i][l] + dp[j][i - 1][l - 1]
    
    
print(dp[0][len(N)-1][K]+dp[1][len(N)-1][K])

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

dp=[[[0 for _ in range(4)] for _ in range(len(N))] for _ in range(2)]
for i in range(len(N)):
    num=N[i]
    mayover=0
    if i==0:
        for j in range(10):
            if j<num:
                if j==0:
                    dp[0][i][0]=dp[0][i][0]+1
                else:
                    dp[0][i][1] = dp[0][i][1] + 1
            elif j==num:
                if j==0:
                    dp[1][i][0] = dp[1][i][0] + 1
                else:
                    dp[1][i][1] = dp[1][i][1] + 1
    else:

        for j in range(2):
            if j==0:
                for l in range(4):
                    dp[j][i][l] = dp[j][i][l] + dp[j][i - 1][l]
                    if l != 0:
                        dp[j][i][l] = dp[j][i][l] + 9*dp[j][i - 1][l - 1]
            else:
                if num==0:
                    for l in range(4):
                        dp[j][i][l]=dp[j][i-1][l]
                else:
                    for l in range(4):
                        dp[0][i][l]=dp[0][i][l]+dp[j][i-1][l]
                        if l!=0:
                            dp[0][i][l]=dp[0][i][l]+(num-1)*dp[j][i-1][l-1]
                            dp[1][i][l]=dp[1][i][l]+dp[j][i-1][l-1]

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

Solution (Python):
import sys
 
read = sys.stdin.read
 
 
def main():
    N, K = map(int, read().split())
 
    dp1 = [0] * (K + 1)
    dp2 = [0] * (K + 1)
    dp1[0] = 1
 
    for x in map(int, str(N)):
        for j in range(K, -1, -1):
            if j > 0:
                dp2[j] += dp2[j - 1] * 9
                if x != 0:
                    dp2[j] += dp1[j - 1] * (x - 1) + dp1[j]
                    dp1[j] = dp1[j - 1]
            else:
                dp1[j] = 0
                dp2[j] = 1
 
    print(dp1[K] + dp2[K])
    return
 
 
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]

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

Solution (Python):
import math
n = int(input())
K = int(input())

def calk1(n):
    if n == 0: return 0
    m = int(math.log10(n))
    num = m * 9
    num += n//(10**m)
    return num

def calk2(n):
    m = int(math.log10(n))
    num = m * (m - 1) // 2 * 9**2
    num += (n//(10**m)-1) * m * 9
    num += calk1(n - (n//(10**m)*10**m))
    return num

def calk3(n):
    m = int(math.log10(n))
    num = m * (m - 1) * (m - 2) // 6 * 9**3
    num += (n//(10**m)-1) * (m * (m - 1) // 2 * 9**2)
    num += calk2(n - (n//(10**m)*10**m))
    return num
if n < 10 ** (K - 1): print(0)
else:
    if K == 1: print(calk1(n))
    elif K == 2: print(calk2(n))
    else: print(calk3(n))

Solution (Python):




import math

import itertools
from collections import deque
from collections import Counter



import bisect
n=input()
k=int(input())
if k==1:
    a=int(n[0])
    l=len(n)
    ans=9*(l-1)+a
elif k==2:
    a=int(n[0])
    A=len(n)
    for i in range(1,A):
        if n[i]!="0":
            b=int(n[i])
            B=A-i
            break
    else:
        B=1
        b=0
    ans=9*(a-1)*(A-1)+(B-1)*9+b
    for i in range(2,A):
        ans+=81*(i-1)
else:
    a=int(n[0])
    A=len(n)
    for i in range(1,A):
        if n[i]!="0":
            b=int(n[i])
            B=A-i
            for j in range(i+1,A):
                if n[j]!="0":
                    c=int(n[j])
                    C=A-j
                    break
            else:
                c=0
                C=1
            break
    else:
        c=b=0
        C=B=1
    ans=(a-1)*81*(A-1)*(A-2)//2+81*(B-1)*(B-2)//2+(b-1)*9*(B-1)+9*(C-1)+c
    for i in range(3,A):
        ans+=729*(i-1)*(i-2)//2
print(ans)

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


def run():
    dp = [[[0] * 4 for _ in range(2)] for _ in range(len(sN) + 1)]
    dp[0][0][0] = 1

    for i in range(len(sN)):
        for j in range(2):
            
            

            
            lim = 9 if j == 1 else (ord(sN[i]) - ord('0'))
            for k in range(lim + 1):
                for l in range(4):
                    nl = l + int(k > 0)
                    if nl >= 4: continue
                    dp[i + 1][k < lim or j == 1][nl] += dp[i][j][l]

        

    print(dp[len(sN)][0][K] + dp[len(sN)][1][K])


if __name__ == '__main__':
    run()

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


dp[0][0][1] = 1
for i in range(1, len_n+1):
    d = int(n[i-1])
    for j in range(K+1):
        dp[i][j][0] += dp[i-1][j][0]
        dp[i][j+1][0] += dp[i-1][j][0]*9
        if 0 < d:
            dp[i][j+1][0] += dp[i-1][j][1]*(d-1)
            dp[i][j][0] += dp[i-1][j][1]
            dp[i][j+1][1] += dp[i-1][j][1]
        else:
            dp[i][j][1] += dp[i-1][j][1]

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

Solution (Python):

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

    
    
    
    

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

    for i in range(n):
        for j in range(4):
            for k in range(2):
                nd = int(S[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]
    ans = dp[n][K][0] + dp[n][K][1]
    print(ans)


if __name__ == "__main__":
    resolve()

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

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

dp[0][0][0] = 1
dp[0][1][0] = 0
dp[0][2][0] = 0
dp[0][3][0] = 0
dp[0][0][1] = 0
dp[0][1][1] = 0
dp[0][2][1] = 0
dp[0][3][1] = 0

for i in range(1, keta+1):
    n = int(str(N)[i-1])
    if n == 0:
        
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][1][0] = dp[i-1][1][0]
        dp[i][2][0] = dp[i-1][2][0]
        dp[i][3][0] = dp[i-1][3][0]
        
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][1][1] = dp[i-1][1][1] + dp[i-1][0][1]*9
        dp[i][2][1] = dp[i-1][2][1] + dp[i-1][1][1]*9
        dp[i][3][1] = dp[i-1][3][1] + dp[i-1][2][1]*9
    elif n != 0:
        dp[i][0][0] = 0
        dp[i][1][0] = dp[i-1][0][0]
        dp[i][2][0] = dp[i-1][1][0]
        dp[i][3][0] = dp[i-1][2][0]
        
        dp[i][0][1] = dp[i-1][0][0] + dp[i-1][0][1]
        dp[i][1][1] = (dp[i-1][1][0]+dp[i-1][1][1]) \
                     + dp[i-1][0][0]*(n-1) + dp[i-1][0][1]*9
        dp[i][2][1] = (dp[i-1][2][0]+dp[i-1][2][1]) \
                     + dp[i-1][1][0]*(n-1) + dp[i-1][1][1]*9
        dp[i][3][1] = (dp[i-1][3][0]+dp[i-1][3][1]) \
                     + dp[i-1][2][0]*(n-1) + dp[i-1][2][1]*9
print(sum(dp[keta][K]))

Solution (Python):
import sys
from functools import lru_cache

read = sys.stdin.read


def com(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(n - r + 1, n + 1):
        numer = numer * i
    for i in range(1, r + 1):
        denom = denom * i
    return numer // denom


def main():
    N, K = map(int, read().split())

    S = str(N)
    L = len(S)

    @lru_cache(maxsize=None)
    def rec(i, k, smaller):
        if i == L:
            if k == 0:
                return 1
            else:
                return 0
        if k == 0:
            return 1
        if smaller:
            return com(L - i, k) * pow(9, k)
        if S[i] == '0':
            return rec(i + 1, k, False)

        ans = 0
        ans += rec(i + 1, k, True)
        ans += rec(i + 1, k - 1, True) * (int(S[i]) - 1)
        ans += rec(i + 1, k - 1, False)
        return ans

    ans = rec(0, K, False)

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def com(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(n - r + 1, n + 1):
        numer = numer * i
    for i in range(1, r + 1):
        denom = denom * i
    return numer // denom


def main():
    N, K = map(int, read().split())

    S = str(N)
    L = len(S)

    @lru_cache(maxsize=None)
    def rec(i, k, smaller):
        if i == L:
            if k == 0:
                return 1
            else:
                return 0
        if k == 0:
            return 1
        if smaller:
            return com(L - i, k) * pow(9, k)
        if S[i] == '0':
            return rec(i + 1, k, False)

        ans = 0
        ans += rec(i + 1, k, True)
        ans += rec(i + 1, k - 1, True) * (int(S[i]) - 1)
        ans += rec(i + 1, k - 1, False)
        return ans

    ans = rec(0, K, False)

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

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

    @lru_cache(None)
    def F(n, k):

        if n < 10:
            if 1 < k:
                return 0
            elif k == 1:
                return n
            elif k == 0:
                return 1

        m, r = divmod(n, 10)
        ret = 0
        
        if k >= 1:
            ret += F(m, k-1)*r  
            ret += F(m-1, k-1)*(9-r)  
        ret += F(m, k)*1  
        return ret
    print(F(n, k))


resolve()

Solution (Python):
import sys

read = sys.stdin.read


def main():
    N, K = map(int, read().split())

    dp1 = [0] * (K + 1)
    dp2 = [0] * (K + 1)
    dp1[0] = 1

    for x in map(int, str(N)):
        for j in range(K, -1, -1):
            if j > 0:
                dp2[j] += dp2[j - 1] * 9
                if x != 0:
                    dp2[j] += dp1[j - 1] * (x - 1) + dp1[j]
                    dp1[j] = dp1[j - 1]
            else:
                dp1[j] = 0
                dp2[j] = 1

    print(dp1[K] + dp2[K])
    return


if __name__ == '__main__':
    main()