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 math
n=int(input())
k=int(input())

def comb(n,k):
    s=1
    for i in range(k):
        s*=n-i
    for i in range(k):
        s//=i+1
    return s

def ans(n,k):

    s=0
    if int(str(n)[0])==0:
        return 0
    if len(str(n))<k:
        return 0
    elif len(str(n))==k:
        s+=(int(str(n)[0])-1) * comb(len(str(n))-1,k-1)*9**(k-1)
        if k-1==0:
            s+= 1
        else:
            s+= ans(int(str(n)[1:]),k-1)
        return s
    else:
        s += (int(str(n)[0]) - 1) * comb(len(str(n)) - 1, k - 1) * 9 ** (k - 1)
        if k-1==0:
            s+= 1
        else:
            s+= ans(int(str(n)[1:]),k-1)
        s+=comb(len(str(n))-1,k)*9**(k)
        return s

print(ans(n,k))

Solution (Python):
def nCkpow(n,k):
    if n<k:
        return 0
    y=1
    for i in range(k):
        y*=n-i
        y//=i+1
        y*=9
    return y
def f(s,m,k):
    
    if len(s)-m<k:
        return 0
    if  k==0:
        return 1
    if s[m]=='0':
        return f(s,m+1,k)
    l=len(s)-m
    y=nCkpow(l-1,k)
    y+=(int(s[m])-1)*nCkpow(l-1,k-1)
    return y+f(s,m+1,k-1)
N=input()
K=int(input())
print(f(N,0,K))

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

digit_n = len(n)


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

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

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

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    S=input()
    N=len(S)
    K=I()
    
    dpl=[[0]*(K+1)for _ in range(N+1)]
    dpt=[[0]*(K+1)for _ in range(N+1)]
    
    
    dpt[0][0]=1
    
    for i in range(N):
        
        for j in range(K+1):
            dpl[i+1][j]=dpl[i][j]
            
        for j in range(1,K+1):
            dpl[i+1][j]+=dpl[i][j-1]*9 
            
        s=int(S[i])
        
        if s==0:
            for j in range(K+1):
                dpt[i+1][j]=dpt[i][j]
        else:
            for j in range(1,K+1):
                dpt[i+1][j]=dpt[i][j-1]
            
            
            for j in range(K+1):
                dpl[i+1][j]+=dpt[i][j]
            
            for j in range(K):
                dpl[i+1][j+1]+=dpt[i][j]*(s-1)
                
    ans=dpt[-1][-1]+dpl[-1][-1]
    
    print(ans)
    
    
    
        
    
    
    
                
            
            
        
        

main()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect


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

def main():
    N = S()
    K = I()
    dig = len(N)
    if dig < K:
        print(0)
        exit()
    ans = 0
    for i in range(dig):
        if K == 0:
            ans += 1
            break
        if int(N[i]) == 0:
            continue
        if dig - i - 1 >= K:
            ans += combinations_count(dig - i - 1, K) * pow(9, K)
        if dig - i - 1 >= K - 1:
            ans += (int(N[i]) - 1) * combinations_count(dig - i - 1, K - 1) * pow(9, K - 1)
        if i == dig - 1:
            ans += 1
        K -= 1
    print(ans)
if __name__ == "__main__":
    main()

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 = input()
k = int(input())
l = len(n)




dp = [[[0]*2 for j in range(k+1)] for i in range(l+1)]
dp[0][0][0] = 1
for i in range(l):
    ni = int(n[i])
    for j in range(k+1):
        for st in range(2):
            for x in range(10):
                i_ = i+1
                j_ = j
                st_ = st
                if x != 0:
                    j_ += 1
                if j_ > k:
                    continue
                if st_ == 0 and x > ni:
                    continue
                if st_ == 0 and x < ni:
                    st_ = 1
                dp[i_][j_][st_] += dp[i][j][st]

print(sum(dp[l][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):
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):
        if k-1>=0:
            if l!=0:
                dp[i][0][k]=dp[i-1][0][k-1]
                dp[i][1][k] = dp[i-1][1][k] + 9 * dp[i-1][1][k-1]+dp[i-1][0][k] + (l-1) * dp[i-1][0][k-1]
            else:
                dp[i][0][k] = dp[i-1][0][k]
                dp[i][1][k] = dp[i-1][1][k] + 9 * dp[i-1][1][k-1]
        else:
            dp[i][0][k] = 0
            dp[i][1][k] = 1

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

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

l = len(N)

dp = [[[0]*(K+1) for _ in range(2)] for _ in range(l)]
dp[0][0][1] = 1
dp[0][1][1] = int(N[0]) - 1
dp[0][1][0] = 1


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

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

Solution (Python):

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def per(n, r, mod=10**9+7):  
    per = 1
    for i in range(r):
        per = per*(n-i) % mod
    return per


def com(n, r, mod=10**9+7):  
    bunshi = per(n, r, mod)
    bunbo = 1
    for i in range(1, r+1):
        bunbo = bunbo*i % mod
    return bunshi*pow(bunbo, -1, mod) % mod


def main():
    n = list(map(int, list(input())))
    k = int(input())
    keta = len(n)
    count = [n[0]-1+com(keta-1, 1)*9, (n[0]-1)*com(keta-1, 1)*9+com(keta-1, 2)
             * 9**2, (n[0]-1)*com(keta-1, 2)*9**2+com(keta-1, 3)*9**3]
    nonzero = 1
    
    for i in range(1, keta):
        if n[i] != 0:
            nonzero+=1
            if nonzero==2:
                count[1]+=(n[i]-1)+com(keta-i-1,1)*9
                count[2]+=(keta-i-1)*(n[i]-1)*9+com(keta-i-1,2)*9**2
            elif nonzero==3:
                count[2]+=(n[i]-1)+com(keta-i-1,1)*9
        
    print(count[k-1]+(nonzero>=k))



if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
s = "0" + str(N)
n = len(str(N))
K = int(input())

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

for i in range(1, n + 1):
    for k in range(K + 1):
        num = int(s[i])
        if num == 0:
            dp[i][0][k] += dp[i-1][0][k]
        else:
            dp[i][0][k] += dp[i-1][0][k-1]
            dp[i][1][k] += dp[i-1][0][k-1] * (num-1)
            dp[i][1][k] += dp[i-1][0][k]

        dp[i][1][k] += 9 * dp[i-1][1][k-1]
        dp[i][1][k] += dp[i-1][1][k]

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

Solution (Python):
N = int(input())
K = int(input())
l = len(str(N))
ans = 0

def neq(n):
    r = 0
    for i in range(10**(len(str(n))-1),n+1):
        ml = 1
        for j in range(len(str(n))):
            ml *= int(str(i)[j])
        if ml != 0:
            r += 1
    return(r)

if l == K:
    print(neq(N))

elif K == 3:
    for i in range(l-2):
        for j in range(i+1,l-1):
            for k in range(j+1,l):
                if i == 0:
                    ans += (int(str(N)[0])-1)*9**2
                    if int(str(N)[1:max(j,2)])>0 and j != 1:
                        ans += 9**2
                    else:
                        if int(str(N)[j+1:max(k,j+2)])>0 and k != j+1:
                                ans += int(str(N)[j])*9
                        else:
                            if int(str(N)[j])*int(str(N)[k]) != 0:
                                ans += neq(int(str(N)[j])*10+int(str(N)[k]))
                            
                else:
                    ans += 9**3
    print(ans)

elif K == 2:
    for i in range(l-1):
        for j in range(i+1,l):
            if i == 0:
                ans += (int(str(N)[0])-1)*9
                if int(str(N)[1:max(j,2)])>0 and j != 1:
                        ans += 9
                else:
                    ans += int(str(N)[j])

            else:
                ans  += 9**2
    print(ans)

else:
    for i in range(l):
        if i == 0:
            ans += int(str(N)[0])
        else:
            ans += 9
    print(ans)

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

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): 
        if k == 0: 
            dp[i][0][k] = 0 
            dp[i][1][k] = 1 
        else: 
            if l != 0: 
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: 
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]


print(dp[m][0][K] + dp[m][1][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): 
        if k -1 >= 0:
            if l != 0: 
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: 
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]
        else: 
            dp[i][0][k] = 0 
            dp[i][1][k] = 1 


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

Solution (Python):
n=int(input())
k=int(input())
def main(N,K):
  ans=0
  if N<=100+10**6:
    for i in range(1,N+1):
      a=str(i)
      if len(a)-list(a).count("0")==K:
        ans+=1
    return ans
  L=list(map(int,list(str(N))))
  ans=0
  L=list(map(int,list(str(N))))
  if K==1:
    return (len(str(N))-1)*9+int(str(N)[0])
  elif K==2:
    for i in range(len(L)-1):
      ans+=(9*(int(str(N)[0])-1))
      for j in range(i+1,len(L)):
        if i==0:
          if j==1:
            ans+=int(str(N)[1])
          else:
            ans+=9
        else:
          ans+=81
    return ans
  else:
    le=len(L)
    for i in range(le-2):
      for j in range(i+1,le-1):
        for k in range(j+1,le):
          if i==0:
            ans+=81*(int(str(N)[0])-1)
            if j==1:
              ans+=9*(int(str(N)[1])-1)
              if k==2:
                ans+=int(str(N)[2])
              else:
                ans+=9
            else:
              ans+=81
          else:
            ans+=729
    return ans
ans2=0
L=list(str(n))
a=len(L)
for i in range(a):
  L=list(str(n))
  s=L[:a-i-1]
  t=L[a-i-1:]
  t=int("".join(t))
  p=s.count("0")
  p=len(s)-p
  if p>k:
    n-=t+1
  elif p==k:
    n-=t+1
    ans2+=1
  else:
    ans2+=main(t,k-p)
    n-=t+1
print(ans2)

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

dp0 = [0]*3
dp1 = [[0]*3]*len(n)
dp0[0] = 1
dp1[0][0] = max(0, n[0]-1)
for i in range(1, len(n)):
    dp1[i] = [
        dp1[i-1][0]+dp0[0]*(n[i]!=0)+9,
        dp1[i-1][1]+dp0[1]*(n[i]!=0)+dp0[0]*max(0, n[i]-1)+dp1[i-1][0]*9,
        dp1[i-1][2]+dp0[2]*(n[i]!=0)+dp0[1]*max(0, n[i]-1)+dp1[i-1][1]*9,
    ]
    if n[i] != 0:
        dp0 = [0]+dp0[:2]
print(dp0[k-1]+dp1[-1][k-1])

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

dp0 = [[0]*3]*len(n)
dp1 = [[0]*3]*len(n)
dp0[0][0] = 1
dp1[0][0] = max(0, n[0]-1)
for i in range(1, len(n)):
    if n[i]==0:
        dp0[i] = dp0[i-1]
    else:
        dp0[i] = [0]+dp0[i-1][:2]

    dp1[i] = [
        dp1[i-1][0]+dp0[i-1][0]*(n[i]!=0)+9,
        dp1[i-1][1]+dp0[i-1][1]*(n[i]!=0)+dp0[i-1][0]*max(0, n[i]-1)+dp1[i-1][0]*9,
        dp1[i-1][2]+dp0[i-1][2]*(n[i]!=0)+dp0[i-1][1]*max(0, n[i]-1)+dp1[i-1][1]*9,
    ]

print(dp0[-1][k-1]+dp1[-1][k-1])

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

dp0 = [[0]*3]*len(n)
dp1 = [[0]*3]*len(n)
dp0[0][0] = 1
dp1[0][0] = max(0, n[0]-1)
for i in range(1, len(n)):
    if n[i]==0:
        dp0[i] = dp0[i-1]
    else:
        dp0[i] = [0]+dp0[i-1][:2]

    dp1[i] = [
        dp1[i-1][0]+dp0[i-1][0]*(n[i]!=0)+9,
        dp1[i-1][1]+dp0[i-1][1]*(n[i]!=0)+dp0[i-1][0]*max(0, n[i]-1)+dp1[i-1][0]*9,
        dp1[i-1][2]+dp0[i-1][2]*(n[i]!=0)+dp0[i-1][1]*max(0, n[i]-1)+dp1[i-1][1]*9,
    ]

print(dp0[-1][k-1]+dp1[-1][k-1])

Solution (Python):
import functools
import sys


@functools.lru_cache(None)
def doit(n, k):
    if len(n) == 0 or k < 0:
        return k == 0
    d = int(n[0])
    return sum(doit(n[1:] if i == d else '9' * (len(n) - 1), k - 1 if i > 0 else k) for i in range(d + 1))


sys.setrecursionlimit(404)
print(doit(input(), int(input())))

Solution (Python):
import sys
sys.setrecursionlimit(303)


def doit(n, k, m):
    if len(n) == 0 or k < 0:
        return k == 0
    if (n, k) not in m:
        d = int(n[0])
        m[(n, k)] = sum(doit(n[1:] if i == d else '9' * (len(n) - 1), k - 1 if i > 0 else k, m) for i in range(d + 1))
    return m[(n, k)]


print(doit(input(), int(input()), {}))

Solution (Python):
import sys
sys.setrecursionlimit(10000)

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


def doit(n, k):
    if len(n) == 0:
        return k == 0
    d = int(n[0])
    if (n, k) not in m:
        ret = 0
        for i in range(d + 1):
            if i == d:
                ret += doit(n[1:], k - 1 if i > 0 else k)
            else:
                ret += doit('9' * (len(n) - 1), k - 1 if i > 0 else k)
        m[(n, k)] = ret
    return m[(n, k)]


print(doit(n, k))

Solution (Python):
from itertools import combinations
N=input()
K=int(input())
L = len(N)
dp = [[[0]*(L+1) for _ in range(K+2)] for _ in range(2)]




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

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

Solution (Python):
def nCk(n, k):
    if k > n or min(n, k) < 0:
        return 0
    res = 1
    for i in range(1, k + 1):
        res = res * (n - i + 1) // i
    return res

def solveSmaller():
    return 9 ** k * nCk(n - 1, k)

def solveDp():
    global k
    dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n)]  
    dp[0][1][0] = 1
    dp[0][1][1] = int(s[0]) - 1
    cnt = 1
    for i in range(1, n):
        cnt += s[i] != '0'
        for k in range(1, k + 1):
            dp[i][k][0] = cnt == k
            dp[i][k][1] = dp[i - 1][k][1] + \
                          (dp[i - 1][k][0] if s[i] != '0' else 0) + \
                          dp[i - 1][k - 1][1] * 9 + \
                          dp[i - 1][k - 1][0] * max(0, int(s[i]) - 1)
    return dp[n - 1][k][0] + dp[n - 1][k][1]

s = input()
k = int(input())
n = len(s)
print(solveSmaller() + solveDp())

Solution (Python):
n = list(reversed(input()))
k = int(input())
dp1 = [1] + [0] * 3
dp2 = [1] + [0] * 3
for i in range(len(n)):
    newdp1 = [0] * 4
    newdp2 = [0] * 4
    for j in range(4):
        newdp2[j] += dp2[j]
        if j > 0:
            newdp2[j] += dp2[j - 1] * 9
        d = int(n[i])
        if d == 0:
            newdp1[j] += dp1[j]
        else:
            newdp1[j] += dp2[j]
        if j > 0:
            if d > 0:
                newdp1[j] += dp1[j - 1]
                newdp1[j] += dp2[j - 1] * (d - 1)
    dp1 = newdp1
    dp2 = newdp2
print(dp1[k])

Solution (Python):
str_n = input()
keta = len(str_n)
not_zero = int(input())

dp = [[[0]*(not_zero+2) for _ in range(2)] for _ in range(keta+1)]
first = int(str_n[0])
dp[1][1][0] = 1
for k in range(1,10):
    if first == k:
        dp[1][0][1] += 1
    elif first > k:
        dp[1][1][1] += 1

for i in range(1,keta):
    
    for j in range(not_zero+1):
        
        dp[i+1][1][j] += dp[i][1][j]
        
        dp[i+1][1][j+1] += (dp[i][1][j])*9

    nex = int(str_n[i])
    
    if not nex == 0:
        for j in range(not_zero+1):
            
            dp[i+1][1][j] += dp[i][0][j]
            
            dp[i+1][1][j+1] += (dp[i][0][j]) * (nex-1)
    
    
    if nex == 0:
        for j in range(not_zero+1):
            dp[i+1][0][j] = dp[i][0][j]
    else:
        for j in range(not_zero):
            dp[i+1][0][j+1] = dp[i][0][j]

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

Solution (Python):
n=input()
ln=len(n)
nn=[-1,-1,-1]
nnn=[0,0,0]
j=0
for i in range(ln):
  if n[i]!="0":
    nn[j]=i
    nnn[j]=int(n[i])
    j+=1
    if j==3:
      break

s=[9*(ln-1),81*(ln-1)*(ln-2)//2,729*(ln-1)*(ln-2)*(ln-3)//6]
s[0]+=nnn[0]
s[1]+=(nnn[0]-1)*9*(ln-1)+(0 if nn[1]==-1 else nnn[1]+9*(ln-nn[1]-1))
s[2]+=(nnn[0]-1)*81*(ln-1)*(ln-2)//2
s[2]+=(0 if nn[1]==-1 else (nnn[1]-1)*9*(ln-nn[1]-1)+81*(ln-nn[1]-1)*(ln-nn[1]-2)//2)+(0 if nn[2]==-1 else nnn[2]+9*(ln-nn[2]-1))

k=int(input())
print(s[k-1])

Solution (Python):



"""
memo
dp0[i][j]
  上からi桁目まで決めて，0でない桁がj個あり
  Nより小さいことが確定している (less)
dp1[i][j]
  上からi桁目まで決めて，0でない桁がj個あり
  Nより小さいことが確定していない (i桁目まで同じ)

通常の再帰
rec
"""

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


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


for i in range(N):
    dig = int(S[i])

    
    for j in range(K + 1): 
        
        for k in range(10):
            nj = j if k == 0 else j + 1
            if k < dig:
                dp1[i + 1][nj] += dp0[i][j] + dp1[i][j]
            elif k == dig:
                dp1[i + 1][nj] += dp1[i][j]
                dp0[i + 1][nj] += dp0[i][j]
            else:
                dp1[i + 1][nj] += dp1[i][j]

ans = dp0[N][K] + dp1[N][K]
print(ans)

Solution (Python):



"""
memo
dp0[i][j]
  上からi桁目まで決めて，0でない桁がj個あり
  Nより小さいことが確定している (less)
dp1[i][j]
  上からi桁目まで決めて，0でない桁がj個あり
  Nより小さいことが確定していない (i桁目まで同じ)

通常の再帰
rec
"""

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

def com(N, R):
    if R < 0 or R > N:
        return 0
    if R == 1:
        return N
    elif R == 2:
        return N * (N - 1) // 2
    elif R == 3:
        return N * (N - 1) * (N - 2) // 6
    else:
        raise NotImplementedError("NIE")



def rec(i, k, smaller):
    if i == N:
        return 1 if k == 0 else 0
    if k == 0:
        return 1
    if smaller:
        
        return com(N - i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i + 1, k , False)
        else:
            zero = rec(i + 1, k, True)
            aida = rec(i + 1, k - 1, True) * (int(S[i]) - 1)
            ichi = rec(i + 1, k - 1, False)
            return zero + aida + ichi

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

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)




def get_dp_target(string: str) -> []:
    return [0] + list(map(int, list(string)))



def resolve(test_def_name=""):
    try:
        
        n = get_dp_target(input())

        target = int(input())

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

        
        for i in range(n[1] + 1):
            
            is_smaller = True if i < n[1] else False
            
            
            not_zero_count = 0 if i == 0 else 1
            dp[1][is_smaller][not_zero_count] += 1

        
        
        for place in range(2, len(n)):

            
            for is_smaller in range(2):

                
                for not_zero_count in range(100):
                    
                    val_range = 10 if is_smaller else n[place] + 1
                    for val in range(val_range):
                        
                        work_is_smaller = is_smaller or val < n[place]
                        work_not_zero_count = not_zero_count if val == 0 else not_zero_count + 1
                        dp[place][work_is_smaller][work_not_zero_count] += dp[place - 1][is_smaller][not_zero_count]

        print(dp[len(n) - 1][0][target] + dp[len(n) - 1][1][target])
    except IndexError as err:
        print("インデックスエラー:", err.args[0])



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """100
1"""
        output = """19"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """25
2"""
        output = """14"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """314159
2"""
        output = """937"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3"""
        output = """117879300"""
        self.assertIO(test_input, output)

    
    def test_original(self):
        pass



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


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

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

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

        if N[i] != "0":
            dp[i+1][0][k] += dp[i][1][k]
            dp[i+1][0][k+1] += dp[i][1][k]*(int(N[i])-1)
            dp[i+1][1][k+1] += dp[i][1][k]
        else:
            dp[i+1][1][k] += dp[i][1][k]

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

Solution (Python):
import math


def comb(n, r):
    if n < r or r < 0:
        return 0
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume *= (n - i + 1)
        deno *= (i)
    return nume//deno


def solve(N, K):
    if N < K:
        return 0
    if K == 0:
        return 1
    keta = math.floor(math.log(N, 10)) + 1
    x = N//pow(10, keta-1)
    ret = 0
    if K > keta:
        return 0
    
    if keta != K:
        ret += comb(keta - 1, K) * (9 ** K)
    
    ret += (x-1)*comb(keta-1, K-1)*pow(9, K-1)
    
    ret += solve(N % pow(10, keta-1), K - 1)
    return ret


N = int(input())
K = int(input())
ans = solve(N, K)
print(ans)

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
k = INT()

@lru_cache(None)
def F(n, k):
    
    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):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
k = INT()

@lru_cache(None)
def F(n, k):
    
    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 bisect, collections, copy, functools, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    K = I()

    
    @functools.lru_cache
    def f(N, K):
        if N == K == 0:
            ret = 1
        elif N > 0 and K >= 0:
            ret = f(N // 10, K) + N % 10 * f(N // 10, K - 1) + (9 - N % 10) * f(N // 10 - 1, K - 1)
        else:
            ret = 0
        return ret
    
    ans = f(N, K)
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve(n, k, m):
    ans = 0
    for i in range(k, m):
        
        if k == 1:
            ans += 9
        else:
            ans += pow(9, k)*comb(i-1, k-1)
    if k == 1:
        ans += int(n[0])
    elif k == 2:
        ans += (int(n[0])-1)*pow(9, k-1)*comb(m-1, k-1)
        j = 1
        while j < m and n[j] == '0':
            j += 1
        if j < m:
            ans += int(n[j]) + pow(9, k-1)*comb(m-1-j, k-1)
    else:
        while m >= k and n.count('0') > m - k:
            n = str(int(n)-1)

        if m > len(n):
            print(ans)
            return ans

        m = len(n)
        a = []
        for i in range(m):
            if len(a) < 3 and n[i] != '0':
                a.append(i)

        if len(a) == 3:
            ans += 1 + int(n[a[2]])-1 + 9*comb(m-1-a[2], 1)
            ans += (int(n[a[1]])-1)*9*comb(m-1-a[1], 1) + 9*9*comb(m-1-a[1], 2)
            ans += (int(n[a[0]])-1)*9*9*comb(m-1-a[0], 2)
    print(ans)
    return ans

def solve2(n, k, m):
    ans = 0
    for i in range(1, int(n)+1):
        if len(str(i)) - str(i).count('0') == k:
            ans += 1
    print(ans)
    return ans

if __name__ == '__main__':
    n = input()
    k = INT()
    m = len(n)

    solve(n,k,m)