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) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    s = input()
    K= int(input())
    
    
    
    
    keta=len(s)
    dp=[[[0,0] for _ in range(keta+1)] for _ in range(keta+1)]
    

    dp[0][0][0]=1
    for i in range(0,keta):
        ni=i+1
        nd=int(s[i])
        for j in range(0,keta):
            for k in range(0,2):  
                for d in range(10): 
                    nj=j
                    nk=k
                    if d!=0:nj+=1
                    if k==0:
                        if d>nd:break
                        elif d<nd:nk=1
                    dp[ni][nj][nk]+=dp[i][j][k]
    if K<=keta:
        ans=dp[keta][K][1]+dp[keta][K][0]
    else:
        ans=0
        
    print(ans)
    


    
    

        
    



if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    N = input()
    K= int(input())
    
    
    
    
    keta=100+1
    dp=[[0]*(keta+1) for _ in range(keta+1)]
    dp[0][0]=1

    for i in range(1,keta+1):
        for j in range(0,i+1):
            dp[i][j]+=dp[i-1][j]+dp[i-1][j-1]*9
    l=len(N)
    cur0=0
    tot=0
    for i,si in enumerate(N):
        n=int(si)
        if n!=0:
            tot+=(n-1)*dp[l-1-i][K-i-1+cur0]+dp[l-1-i][K-i+cur0]
        else:
            cur0+=1
    ic=0
    for s in N:
        if s!='0':ic+=1
    if ic==K:tot+=1
    print(tot)
    

        
    



if __name__ == "__main__":
    main()

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

def pow(a,n):
    ans = 1
    while n > 1:
        if bin(a&1)==bin(1):
            ans = ans*a
        a = a*a
        n = n>>1
    return ans

def com(N,k):
    if k<0 or k>N: return 0
    if k==1:return N
    elif k==2: return N*(N-1)//2
    else: return N*(N-1)*(N-2)//6

S = len(str(N))
N = str(N)
def helper(i,k,smaller):
    if i==S:
        if k==0: return 1
        else: return 0
    if k ==0: return 1
    if smaller: return com(S-i,k)*(9**k)
    else:
        if N[i]=='0': return helper(i+1,k,False)
        else:
            zero = helper(i+1,k,True)
            a = helper(i+1,k-1,True)*(int(N[i])-1)
            b = helper(i+1,k-1,False)
            return zero + a + b
print(helper(0,K,False))

Solution (Python):
n,K=input(),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+1] +=DP[i-1][flag][j]
                else:DP[i][flag or k<num][j] +=DP[i-1][flag][j]

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

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    N=input().strip("\n")
    K=int(input())
    
    dp=[[[0]*(2) for i in range(K+1)] for j in range(len(N))]
    dp[0][0][1]=1
    dp[0][1][1]=int(N[0])-1
    dp[0][1][0]=1
    for i in range(len(N)):
        dp[i][0][1]=1
    for i in range(1,len(N)):
        d=int(N[i])
        for j in range(1,K+1):
            if d!=0:
                dp[i][j][1]=dp[i-1][j-1][1]*9+dp[i-1][j-1][0]*(d-1)
                
                
                dp[i][j][1]+=dp[i-1][j][1]+dp[i-1][j][0]
                
                
                dp[i][j][0]=dp[i-1][j-1][0]
                
            else:
                dp[i][j][1]=dp[i-1][j-1][1]*9+dp[i-1][j][1]                
                dp[i][j][0]=dp[i-1][j][0]
    print(sum(dp[len(N)-1][K]))
    
        
    
if __name__=="__main__":
    main()

Solution (Python):
import numpy as np

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

n = len(N)
dp0 = np.zeros((n, K+1), np.int64)
dp1 = np.zeros((n, K+1), np.int64)

dp0[0, 0] = 1
dp0[0, 1] = int(N[0]) - 1
dp1[0, 1] = 1
for i, d in enumerate(N[1:]):
    dp0[i+1] += dp0[i]
    dp0[i+1, 1:] += dp0[i, :-1] * 9
    if int(d) == 0:
        dp1[i+1] = dp1[i]
    elif int(d) == 1:
        dp0[i+1] += dp1[i]
        dp1[i+1, 1:] = dp1[i, :-1]
    elif int(d) >= 2:
        dp0[i+1] += dp1[i]
        dp0[i+1, 1:] += dp1[i, :-1] * (int(d) - 1)
        dp1[i+1, 1:] = dp1[i, :-1]

print(dp0[-1, K] + dp1[-1, K])

Solution (Python):
import numpy as np

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

dp = np.zeros((len(N)+1, K+1), np.int64)
dp[1, 1] = 1
for d in range(1, len(N)):
    dp[d+1] = dp[d]
    dp[d+1, 1:] += dp[d, :-1]

ans = 0
for i, c in enumerate(N):
    n = len(N)-i
    if c != '0':
        ans += np.sum(dp[:n, K]) * (9 ** K)
        ans += dp[n, K] * (int(c) - 1) * (9 ** (K-1))
        K -= 1
        if K == 0:
            ans += 1
            break

print(ans)

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

@functools.lru_cache(None)
def func(num,counter):
    remain = num%10
    quotient = num//10
    
    
    if counter == 0:
        return 1
    
    if num<10:
        if counter ==1:
            return num
        else:
            return 0

    return func(quotient,counter-1)*remain + func(quotient-1,counter-1)*(9-remain) + func(quotient,counter)

print(func(N,K))

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

@functools.lru_cache()
def func(num,counter):
    remain = num%10
    quotient = num//10
    
    
    if counter == 0:
        return 1
    
    if num<10:
        if counter ==1:
            return num
        else:
            return 0

    return func(quotient,counter-1)*remain + func(quotient-1,counter-1)*(9-remain) + func(quotient,counter)

print(func(N,K))

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


def func(num,counter):
    remain = num%10
    quotient = num//10
    
    
    if counter == 0:
        return 1
    
    if num<10:
        if counter ==1:
            return num
        else:
            return 0

    return func(quotient,counter-1)*remain + func(quotient-1,counter-1)*(9-remain) + func(quotient,counter)

print(func(N,K))

Solution (Python):

import sys

sys.setrecursionlimit(10**4)
from math import factorial

def comb(n, r):
    '''
    >>> comb(2, 1)
    2
    >>> comb(3, 2)
    3
    '''
    if r == 0:
        return 1
    if n == 0 or r > n:
        return 0
    return factorial(n) // factorial(n - r) // factorial(r)

def f(S, i, k):
    
    if k == 0:
        
        return 1
    if len(S) <= i:
        
        return 0
    n = int(S[i])
    if n == 0:
        
        return f(S, i+1, k)
    
    ret = (n - 1) * comb(len(S)-i-1, k-1) * pow(9, k-1)
    ret += comb(len(S)-i-1, k) * pow(9, k)
    
    ret += f(S, i+1, k-1)
    return ret

def solve(S: str, K: int):
    return f(S, 0, K)



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)  
    K = int(next(tokens))  
    print(solve(N, K))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

Solution (Python):
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()

N = list(map(int, input()))
K = int(input())


def solve():

    dp_sm = np.zeros((len(N), K + 1), np.int64)
    dp_lg = np.zeros((len(N), K + 1), np.int64)
    dp_sm[0][0] = 1
    dp_sm[0][1] = N[0] - 1
    dp_lg[0][0] = 0
    dp_lg[0][1] = 1

    for i in range(len(N) - 1):
        for j in range(K + 1):

            dp_sm[i + 1][j] += dp_sm[i][j]

            if N[i + 1] != 0:
                dp_sm[i + 1][j] += dp_lg[i][j]

            if j < K:
                dp_sm[i + 1][j + 1] += dp_sm[i][j] * 9

            if j < K and N[i + 1] != 0:
                dp_sm[i + 1][j + 1] += dp_lg[i][j] * (N[i + 1] - 1)
                dp_lg[i + 1][j + 1] += dp_lg[i][j]

            if N[i + 1] == 0:
                dp_lg[i + 1][j] += dp_lg[i][j]

    print(dp_sm[len(N) - 1][K] + dp_lg[len(N) - 1][K])


if __name__ == '__main__':
    solve()

Solution (Python):


import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():

    N = list(map(int, input()))
    K = int(input())

    if K == 1:
        ans = (len(N) - 1) * 9 + N[0]

    elif K == 2:

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

        ans = (9 ** 2) * (len(N) - 1) * (len(N) - 2) // 2
        ans += (N[0] - 1) * (len(N) - 1) * 9

        for i in range(1, len(N)):
            if N[i] != 0:
                ans += N[i] + (len(N) - i - 1) * 9
                break

    elif K == 3:

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

        ans = (9 ** 3) * (len(N) - 1) * (len(N) - 2) * (len(N) - 3) // 6
        ans += (N[0] - 1) * (9 ** 2) * (len(N) - 1) * (len(N) - 2) // 2

        for i in range(1, len(N) - 1):
            if N[i] != 0:
                ans += (9 ** 2) * (len(N) - i - 1) * (len(N) - i - 2) // 2
                ans += (N[i] - 1) * (len(N) - i - 1) * 9
                for j in range(i + 1, len(N)):
                    if N[j] != 0:
                        ans += N[j] + (len(N) - j - 1) * 9
                        break
                break

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():

    N = list(map(int, input()))
    K = int(input())

    if K == 1:
        ans = (len(N) - 1) * 9 + N[0]

    elif K == 2:

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

        ans = (9 ** 2) * (len(N) - 1) * (len(N) - 2) // 2
        ans += (N[0] - 1) * (len(N) - 1) * 9

        for i in range(1, len(N)):
            if N[i] != 0:
                ans += N[i] + (len(N) - i - 1) * 9
                break

    elif K == 3:

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

        ans = (9 ** 3) * (len(N) - 1) * (len(N) - 2) * (len(N) - 3) // 6
        ans += (N[0] - 1) * (9 ** 2) * (len(N) - 1) * (len(N) - 2) // 2

        for i in range(1, len(N) - 1):
            if N[i] != 0:
                ans += (9 ** 2) * (len(N) - i - 1) * (len(N) - i - 2) // 2
                ans += (N[i] - 1) * (len(N) - i - 1) * 9
                for j in range(i + 1, len(N)):
                    if N[j] != 0:
                        ans += N[j] + (len(N) - j - 1) * 9
                        break
                break

    print(ans)


if __name__ == '__main__':
    solve()

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

K=int(input())

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

for i in range(n):
    ni= int(s[i])

    for k in range(4):
            
            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]

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

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(1, len(n) + 1):
    t = int(n[i-1])
    for j in range(k+1):
        if t != 0:
            if j != 0:
                dp[i][0][j] += dp[i-1][0][j-1]
                dp[i][1][j] += dp[i-1][1][j-1] * 9 + dp[i-1][0][j-1] * (t-1)
            dp[i][1][j] += (dp[i-1][1][j] + dp[i-1][0][j])
        else:
            dp[i][0][j] += dp[i-1][0][j]
            if j != 0:
                dp[i][1][j] += dp[i-1][1][j-1] * 9
            dp[i][1][j] += dp[i-1][1][j]

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

Solution (Python):
n = int(input())
k = int(input())
ns = str(n)
digits = len(ns)
dp = [[[0, 0, 0, 0] for i in range(2)] for i in range(digits + 1)]




dp[0][0][0] = 1
for s in range(digits):
    for t in range(2):
        for u in range(4):
            temp = dp[s][t][u]
            if temp == 0:continue

            if t == 0:
                

                for i in range(int(ns[s]) + 1):
                    if i == int(ns[s]):
                        if i == 0:
                            dp[s + 1][t][u] += temp
                        elif i != 0 and u + 1 < 4:
                            dp[s + 1][t][u + 1] += temp

                    else:
                        if i == 0:
                            dp[s + 1][t + 1][u] += temp
                        elif i != 0 and u + 1 < 4:
                            dp[s + 1][t + 1][u + 1] += temp

            else:
                
                for i in range(10):
                    if i == 0:
                        dp[s + 1][t][u] += temp
                    elif i != 0 and u + 1 < 4:
                        dp[s + 1][t][u + 1] += temp

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

Solution (Python):
def main():
    n = list(input())
    k = int(input())
    N = len(n)
    for i in range(N):
        n[i] = int(n[i])
    dp1 = [[0 for _ in range(k+1)] for _ in range(N+1)]
    dp2 = [[0 for _ in range(k+1)] for _ in range(N+1)]
    dp1[0][0] = 1
    for i in range(N):
        for j in range(k+1):
            dp2[i+1][j] += dp2[i][j]
            if j < k:
                dp2[i+1][j+1] += dp2[i][j]*9
            if n[i]:
                dp2[i+1][j] += dp1[i][j]
                if j == k:
                    continue
                dp1[i+1][j+1] += dp1[i][j]
                dp2[i+1][j+1] += dp1[i][j] * (n[i]-1)
            else:
                dp1[i+1][j] += dp1[i][j]
    print(dp1[N][k]+dp2[N][k])
    
if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
K=int(input())
import sys
sys.setrecursionlimit(10**6)
def solve(N, K):
    if K==1:
        l=len(str(N))
        ans=0
        for i in range(l):
            if i!=l-1:
                ans+=9
            else:
                ans+=int(str(N)[0])
        
        return ans
    else:
        nextK=K-1
        l=len(str(N))
        ini=int(str(N)[0])
        res=ini*(10**(l-1))-1
        
        if l>=K:
            ans=solve(res, K)
        else:
            ans=0
        if l-1>=nextK:
            nextN=int(str(N)[1:])
            ans+=solve(nextN, nextK)
            return ans
        return ans
ans=solve(N,K)
print(ans)

Solution (Python):
N=int(input())
K=int(input())
import sys
sys.setrecursionlimit(10**6)
def solve(N, K):
    if K==1:
        l=len(str(N))
        ans=0
        for i in range(l):
            if i!=l-1:
                ans+=9
            else:
                ans+=int(str(N)[0])
        
        return ans
    else:
        nextK=K-1
        l=len(str(N))
        ini=int(str(N)[0])
        res=ini*(10**(l-1))-1
        
        if l>=K:
            ans=solve(res, K)
            nextN=int(str(N)[1:])
            ans+=solve(nextN, nextK)
            return ans
        else:
            return 0
ans=solve(N,K)
print(ans)

Solution (Python):
N = input()
K = int(input())
ng = [0] * (K + 1)
ok = [0] * (K + 1)

ng[0] = 1
ng_count = 0
for n in N:
    n = int(n)
    if n == 0:
        for k in range(K, 0, -1):
            ok[k] = ok[k] + ok[k - 1] * 9
    else:
        ng_count += 1
        for k in range(K, 0, -1):
            ok[k] = ok[k] + ok[k - 1] * 9 + ng[k - 1] * (n - 1) + ng[k]
        ok[0] = 1
        for k in range(K+1):
            ng[k] = int(k == ng_count)

print(ng[-1] + ok[-1])

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

N.reverse()
n = [0]*100
for i in range(100):
    if 99-i < len(N):
        n[i] = int(N[99-i])

dp2 = [[0]*100 for _ in range(4)]
if n[0] == 0:
    dp2[0][0] = 1
else:
    dp2[1][0] = 1
for i in range(1,100):
    if n[i] == 0:
        for j in range(4):
            dp2[j][i] = dp2[j][i-1]
    else:
        for j in range(1,4):
            dp2[j][i] = dp2[j-1][i-1]

dp1 = [[0]*100 for _ in range(4)]
if n[0] != 0:
    dp1[0][0] = 1
    dp1[1][0] = n[0]-1
for i in range(4):
    for j in range(1,100):
        if i != 0:
            if n[j] != 0:
                dp1[i][j] = dp1[i-1][j-1]*9 + dp1[i][j-1]*1 + dp2[i-1][j-1]*max(0,n[j]-1) + dp2[i][j-1]*1
            else:
                dp1[i][j] = dp1[i-1][j-1]*9 + dp1[i][j-1]*1

        else:
            if n[j] != 0:
                dp1[i][j] = dp1[i][j-1]*1 + dp2[i][j-1]*1
            else:
                dp1[i][j] = dp1[i][j-1]*1

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

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

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

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)

Solution (Python):
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])- 0

            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)

Solution (Python):
from sys import stdin
from functools import lru_cache
N = int(stdin.readline().rstrip())
K = int(stdin.readline().rstrip())

@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
    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 math

def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

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

dpSt = makelist(l, K+1)
dpCa = makelist(l, K+1)

init = int(N[0])
dpSt[0][1] = 1
dpCa[0][0] = 1
dpCa[0][1] = init - 1

for i in range(1, l):
    now = int(N[i])

    if now == 0:
        for k in range(K+1):
            dpSt[i][k] = dpSt[i-1][k]
            dpCa[i][k] = dpCa[i-1][k]
        for k in range(1, K+1):
            dpCa[i][k] += dpCa[i-1][k-1] * 9
    else:
        for k in range(1, K+1):
            dpSt[i][k] = dpSt[i-1][k-1]

        for k in range(K+1):
            dpCa[i][k] += dpSt[i-1][k]
        for k in range(1, K+1):
            dpCa[i][k] += dpSt[i-1][k-1] * max(0, now-1)


        for k in range(K+1):
            dpCa[i][k] += dpCa[i-1][k]
        for k in range(1, K+1):
            dpCa[i][k] += dpCa[i-1][k-1] * 9

ans = dpSt[l-1][K] + dpCa[l-1][K]
print(ans)

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

n = len(N)

dp = [[[0]*2 for _ in range(5)] for _ in range(n+1)]
N0 = int(N[0])
if N0 == 0:
    dp[1][0][0] = 1
    dp[1][0][1] = 0
    dp[1][1][0] = 0
    dp[1][1][1] = 0
else:
    dp[1][0][0] = 0
    dp[1][0][1] = 1
    dp[1][1][0] = 1
    dp[1][1][1] = N0-1

for keta in range(1,n):
    Ni = int(N[keta])
    for k in range(4):
        for smaller in range(2):
            if smaller == 1:
                dp[keta+1][k+1][smaller] += dp[keta][k][smaller]*9
                dp[keta+1][k][smaller] += dp[keta][k][smaller]
            elif smaller == 0:
                if Ni == 0:
                    dp[keta+1][k][smaller] += dp[keta][k][smaller]
                else:
                    dp[keta+1][k][smaller+1] += dp[keta][k][smaller]
                    dp[keta+1][k+1][smaller+1] += dp[keta][k][smaller]*(Ni-1)
                    dp[keta+1][k+1][smaller] += dp[keta][k][smaller]
    
print(dp[n][K][0]+dp[n][K][1])

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

if n<10:
    if k==0:
        print(1)
    elif k==1:
        print(n)
    else:
        print(0)
    exit()







lenn=len(str(n))

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


if int(str(n)[0])==1:
    dp[0][0][0]=1
    dp[0][1][1]=1
else:
    dp[0][0][0]=1
    dp[0][1][0]=int(str(n)[0])-1
    dp[0][1][1]=1



for i in range(lenn-1):
    dp[i+1][0][0]+=dp[i][0][0]
    dp[i+1][1][0]+=dp[i][0][0]*9+dp[i][1][0] 
    dp[i+1][2][0]+=dp[i][1][0]*9+dp[i][2][0] 
    dp[i+1][3][0]+=dp[i][2][0]*9+dp[i][3][0] 
    
    if int(str(n)[i+1])==0:
        dp[i+1][0][1]+=dp[i][0][1]
        dp[i+1][1][1]+=dp[i][1][1]
        dp[i+1][2][1]+=dp[i][2][1]
        dp[i+1][3][1]+=dp[i][3][1]

    elif int(str(n)[i+1])==1:
        dp[i+1][1][1]+=dp[i][0][1]
        dp[i+1][2][1]+=dp[i][1][1]
        dp[i+1][3][1]+=dp[i][2][1]

        dp[i+1][1][0]+=dp[i][1][1]
        dp[i+1][2][0]+=dp[i][2][1]
        dp[i+1][3][0]+=dp[i][3][1]
    else:
        dp[i+1][1][1]+=dp[i][0][1]
        dp[i+1][2][1]+=dp[i][1][1]
        dp[i+1][3][1]+=dp[i][2][1]

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

        dp[i+1][1][0]+=dp[i][0][1]*(int(str(n)[i+1])-1)
        dp[i+1][2][0]+=dp[i][1][1]*(int(str(n)[i+1])-1)
        dp[i+1][3][0]+=dp[i][2][1]*(int(str(n)[i+1])-1)
    

print(sum(dp[-1][k]))

Solution (Python):
n = input()
k = int(input())
digit = len(n)
dp0 = [[0 for i in range(k+1)] for j in range(digit+1)]
dp1 = [[0 for i in range(k+1)] for j in range(digit+1)]

dp1[1][1] = 1
dp0[1][1] = int(n[0])-1
for i in range(1, digit+1):
    dp0[i][0] = 1

for i in range(2, digit+1):
    for j in range(1, k+1):
        num = int(n[i-1])
        if num == 0:
            dp0[i][j] = dp0[i-1][j-1]*9 + dp0[i-1][j]
            dp1[i][j] = dp1[i-1][j] 
        else:
            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]

print(dp0[digit][k] + dp1[digit][k])

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

dp = [[[0] * (k+2) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0] = 1
for i, v in enumerate(num_list):
    for j in range(k+1):
        dp[i+1][1][j] += dp[i][1][j]
        dp[i+1][1][j+1] += dp[i][1][j] * 9

        if v == 0:
            dp[i+1][0][j] += dp[i][0][j]
        else:
            dp[i+1][1][j+1] += dp[i][0][j] * (v - 1)
            dp[i+1][1][j] += dp[i][0][j]
            dp[i+1][0][j+1] += dp[i][0][j]

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

Solution (Python):
'''桁dpの典型問題　n以下の非負整数について条件を満たすものの個数を求める
nより小さいことが確定しているかどうかで場合分けをし、遷移を書いて式にすれば良い。'''
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ns()
k = ni()
dp = [[[0]*2 for _ in range(k+1)] for _ in range(len(n)+1)]
dp[0][0][0] = 1
for i in range(len(n)):
    x = int(n[i])
    for j in range(k):
        dp[i+1][j+1][1] += dp[i][j][1]*9
        dp[i+1][j][1] += dp[i][j][1]
        if x > 0:
            dp[i+1][j][1] += dp[i][j][0]
            dp[i+1][j+1][1] += dp[i][j][0]*(x-1)
            dp[i+1][j+1][0] += dp[i][j][0]
        else:
            dp[i+1][j][0] += dp[i][j][0]
    dp[i+1][k][1] += dp[i][k][1]
    dp[i+1][k][x>0] += dp[i][k][0]
    
    
print(sum(dp[len(n)][k]))

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

l=len(N)

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

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

for i,c in enumerate(N):
    x=int(c)

    for j in range(2):
        for d in range(x+1 if j==1 else 10):
            for k in range(K+1):
                dp[i+1][x==d if j==1 else 0][k+1 if 0<d else k]+=dp[i][j][k]   

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

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

    N = list(map(int, list(input()[:-1])))
    K = int(input())
    L = len(N)

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

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

    print(sum(dp[L][K]))  

if __name__ == '__main__':
    main()

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

    N = list(map(int, list(input()[:-1])))
    K = int(input())
    L = len(N)

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

    from pprint import pprint
    for i, x in enumerate(N):
        for k in range(K + 1):
            
            if x == 0:
                
                dp[i + 1][k][0] += dp[i][k][0]
            else:
                
                dp[i + 1][k][1] += dp[i][k][0]
                
                dp[i + 1][k + 1][1] += dp[i][k][0] * (x - 1)
                
                dp[i + 1][k + 1][0] += dp[i][k][0]
            
            dp[i + 1][k + 1][1] += dp[i][k][1] * 9
            
            dp[i + 1][k][1] += dp[i][k][1]

    print(sum(dp[L][K]))  

if __name__ == '__main__':
    main()

Solution (Python):
import math
import itertools

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

f = len(str(n))

if f < k:
    print(0)
else:
    

    en = 1
    for i in range(k):
        en *= f-1-i

    de = math.factorial(k)


    s = en // de * pow(9, k)


    

    kami = int(str(n)[0])

    en = 1
    for i in range(k-1):
        en *= f-1-i

    de = math.factorial(k-1)


    s += (en // de * pow(9, k-1)) * (kami-1)


    

    keta = list(range(f-1))
    num = list(range(1,10))

    b =  kami * pow(10, f-1)
    m = 0


    if k == 1:
        m = b
        if m <= n:
            s += 1
    else:
        for d in itertools.product(num, repeat=k-1):
            for c in itertools.combinations(keta, k-1):
                m = b
                for i in range(k-1):
                    m +=  d[i] * pow(10, c[i])
                if m <= n:
                    s += 1

    print(s)

Solution (Python):
def main():
    EQ = 0
    LESS = 1

    *S, = map(int, input())
    L = len(S)
    K = int(input())

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

    for i, x in enumerate(S):
        for k in range(K + 1):  
            if x == 0:
                dp[i + 1][k][EQ] += dp[i][k][EQ]  
            else:
                dp[i + 1][k + 1][EQ] += dp[i][k][EQ]  
                dp[i + 1][k + 1][LESS] += dp[i][k][EQ] * (x - 1)  
                dp[i + 1][k][LESS] += dp[i][k][EQ]  
            dp[i + 1][k + 1][LESS] += dp[i][k][LESS] * 9  
            dp[i + 1][k][LESS] += dp[i][k][LESS]  

    print(sum(dp[L][K]))  


if __name__ == '__main__':
    main()

Solution (Python):
S=list(input())
n=len(S)
for i in range(n):
  S[i]=int(S[i])
k=int(input())
dp0=[[0]*(n+1) for i in range(k+1)]
dp0[0][0]=1
s=0
for i in range(n):
  if S[i]!=0:
    s=s+1
    if s==k+1:
      break
    dp0[s][i+1]=1
  else:
    dp0[s][i+1]=1
dp1=[[0]*(n+1) for i in range(k+1)]
for i in range(1,n+1):
  if dp0[0][i]==0:
    dp1[0][i]=1
for i in range(1,k+1):
  for j in range(1,n+1):
    if S[j-1]==0:
      dp1[i][j]=dp0[i-1][j-1]*0+dp0[i][j-1]*0+dp1[i-1][j-1]*9+dp1[i][j-1]
    else:
      dp1[i][j]=dp0[i-1][j-1]*(S[j-1]-1)+dp0[i][j-1]+dp1[i-1][j-1]*9+dp1[i][j-1]
print(dp0[-1][-1]+dp1[-1][-1])

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

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

for i in range(n_len):
    for j in range(k+1):
        
        
        dp[i+1][True][j+1] += dp[i][True][j]*9
        
        
        dp[i+1][True][j] += dp[i][True][j]*1

        
        
        
        if int(n[i]) != 0:
            dp[i+1][True][j+1] += dp[i][False][j]*(int(n[i])-1)
            dp[i+1][True][j] += dp[i][False][j]
            

        
        if int(n[i]) != 0:
            dp[i+1][False][j+1] = dp[i][False][j]
        else:
            dp[i+1][False][j] = dp[i][False][j]

print(dp[-1][False][k] + dp[-1][True][k])