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



Sample input:
100
1


Sample output:
19

Submission status: Accepted

Solution code:
from functools import lru_cache

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

@lru_cache(None)
def rec(n, k):
    if k == 0:
        return 1
    if n < 10:
        if k == 1:
            return n
        else:
            return 0


    m,d = divmod(n,10)

    ret = 0
    ret += d * rec(m,k-1) # 最後の桁は1~dの数字。それより上は再帰
    ret += (9-d)*rec(m-1,k-1) # 最後の桁は(d+1)~9，N以下を守るため最後から2番目の桁から1引く
    ret += rec(m,k) # 最後の桁は0，それより上は再帰

    return ret

print(rec(N,K))

Submission status: Accepted

Solution code:
n = input()
k = int(input())
dp = [[[0,0,0,0],[0,0,0,0]] for i in range(len(n))]
#dp[p]は、p桁目まで見たことを表す（p=0は1桁目を見たことになる）
#dp[p][0]は、p桁目まではnより小さいことが確定している
#dp[p][0or1][count]は、p桁目までの「0以外の桁」の登場回数
#(dp[p][1][count]は、例えばn=10275でdp[2][1][1]だった時に、102の中に0がいくつ入っているかを表す。この場合1）
dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = int(n[0])-1
for i in range(1,len(str(n))):
    if n[i] != '0':
        dp[i][0][0] = 0 #遷移前に同じで、遷移後に0でないものが0個かつ遷移前と同じ遷移はありえない
        dp[i][0][1] = dp[i-1][0][0] #ぴったりの数字(0でない)が入ればOK 下二つも同じ
        dp[i][0][2] = dp[i-1][0][1]
        dp[i][0][3] = dp[i-1][0][2]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][0][0]*(int(n[i])-1)+dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][1][0]*9
        dp[i][1][2] = dp[i-1][0][1]*(int(n[i])-1)+dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][1][1]*9
        dp[i][1][3] = dp[i-1][0][2]*(int(n[i])-1)+dp[i-1][0][3]+dp[i-1][1][3]+dp[i-1][1][2]*9
    else:
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][0][2] = dp[i-1][0][2]
        dp[i][0][3] = dp[i-1][0][3]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][1][0]*9+dp[i-1][1][1]
        dp[i][1][2] = dp[i-1][1][1]*9+dp[i-1][1][2]
        dp[i][1][3] = dp[i-1][1][2]*9+dp[i-1][1][3]
print(dp[len(n)-1][0][k]+dp[len(n)-1][1][k])

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


# 桁DPによる数え上げ
# dp[i][smaller][j] = 上からi桁目までで0でない桁がj個ある数字の数
N = input()
K = I()
l = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(l + 1)]
dp[0][False][0] = 1
for i in range(1, l + 1):
    N_i = int(N[i - 1])
    for smaller in [True, False]:  # smaller := Nより小さいことが確定している
        for j in range(K + 1):
            for d in range((9 if smaller else N_i) + 1):
                if j + (0 if d == 0 else 1) <= K:
                    dp[i][smaller or d < N_i][j + (0 if d == 0 else 1)] += dp[i - 1][smaller][j]

print(dp[l][True][K] + dp[l][False][K])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
dp = [[[0,0,0,0],[0,0,0,0]] for i in range(len(n))] #dp[p][0][count]は、p桁目まではnより小さいことが確定している
#countは「0以外の桁」の登場回数、あくまで各桁に登場したt「以下」の数字かどうかを判定する。dp[p][1]は「〜と同じ」
dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = int(n[0])-1
for i in range(1,len(str(n))):
    if n[i] != '0':
        dp[i][0][0] = 0 #遷移前に同じで、遷移後に0でないものが0個かつ遷移前と同じ遷移はありえない
        dp[i][0][1] = dp[i-1][0][0] #ぴったりの数字(0でない)が入ればOK 下二つも同じ
        dp[i][0][2] = dp[i-1][0][1]
        dp[i][0][3] = dp[i-1][0][2]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][0][0]*(max(0,int(n[i])-1))+dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][1][0]*9
        dp[i][1][2] = dp[i-1][0][1]*(max(0,int(n[i])-1))+dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][1][1]*9
        dp[i][1][3] = dp[i-1][0][2]*(max(0,int(n[i])-1))+dp[i-1][0][3]+dp[i-1][1][3]+dp[i-1][1][2]*9
    else:
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][0][2] = dp[i-1][0][2]
        dp[i][0][3] = dp[i-1][0][3]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][1][0]*9+dp[i-1][1][1]
        dp[i][1][2] = dp[i-1][1][1]*9+dp[i-1][1][2]
        dp[i][1][3] = dp[i-1][1][2]*9+dp[i-1][1][3]
print(dp[len(n)-1][0][k]+dp[len(n)-1][1][k])

Submission status: Accepted

Solution code:
from math import factorial


def nCr(n, r):
    if r <= 0:
        return 0

    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

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

    ans = func(N, K)

    print(ans)

def func(N, K):
    N = N.lstrip('0')
    if len(N) < K:
        return 0

    if K == 0:
        return 1

    n = int(N[0])

    if len(N) == 1:
        if K > 1:
            return 0
        else:
            return n

    ret = 0
    if K > 1:
        ret += func(N[1:], K-1)
    else:
        ret += 1
    l = len(N[1:])

    ret += (n - 1) * func('9' * l, K - 1)
    if l >= K:
        ret += func('9'* l, K)

    # ret += (n - 1) * nCr(l-1, K - 2) * 9 ** (K - 1)
    # ret += nCr(l-1, K - 1) * 9 ** K 

    return ret
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

from math import factorial
def comb(n, r):
  if r < 0 or r > n:
    return 0
  else:
    return factorial(n) // (factorial(n - r) * factorial(r))

# 左から i 桁目以降について、0 以外の値を残り K 個使用可能
# smaller: i 桁目までが 一致している時=False, 小さい時=True  
def solve(i, k, smaller):
  if i == n:
    if k == 0:
      return 1
    else:
      return 0
  if k == 0:
    return 1
  if smaller:
    return comb(n - i, k) * 9 ** k
  else:
    if S[i] == "0":
      return solve(i + 1, k, False)
    else:
      zero = solve(i + 1, k, True)
      aida = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
      icchi = solve(i + 1, k - 1, False)
      return zero + aida + icchi

S = input()  
n = len(S)
k = int(input())
print(solve(0, k, False))

Submission status: Accepted

Solution code:
s=input()
K=int(input())
n=len(s)
dp=[[[0]*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(K+1):
        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 nk==0:
                    if nd<d:
                        continue
                    if nd>d:
                        nk=1
                dp[ni][nj][nk]+=dp[i][j][k]
print(dp[n][K][0]+dp[n][K][1])

Submission status: Accepted

Solution code:
nlist = list(map(int, str(input())))
k = int(input())

helper = {}


def fun(digit, remaining_non_zero, edge_case):
    if str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case) in helper.keys():
        return helper[str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case)]

    if remaining_non_zero < 0:
        return 0
    if digit == 0 and remaining_non_zero == 0:
        return 1
    if digit == 0 and remaining_non_zero >= 1:
        return 0

    if edge_case == True:
        ans = 0
        for i in range(nlist[len(nlist) - digit] + 1):
            if i == 0:
                if nlist[len(nlist) - digit] == 0:
                    ans += fun(digit - 1, remaining_non_zero, True)
                else:
                    ans += fun(digit - 1, remaining_non_zero, False)
            elif i == nlist[len(nlist) - digit]:
                ans += fun(digit - 1, remaining_non_zero - 1, True)
            else:
                ans += fun(digit - 1, remaining_non_zero - 1, False)
        helper[str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case)] = ans
        return ans
    if edge_case == False:
        ans = 0
        for i in range(10):
            if i == 0:
                ans += fun(digit - 1, remaining_non_zero, False)
            else:
                ans += fun(digit - 1, remaining_non_zero - 1, False)
        helper[str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case)] = ans
        return ans

print(fun(len(nlist), k, True))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
K=int(input())

n=(str(N))
dp=[[0]*(K+1) for i in range(len(n))]
dp[0][0]=1
dp[0][1]=int(n[0])


count=1
for i in range(len(n)-1):
    dp[i+1][0]+=dp[i][0]
    dp[i+1][1]+=(dp[i][0])*9
    #print(count)
    for j in range(1,K):
        dp[i+1][j]+=dp[i][j]
        dp[i+1][j+1]+=max((dp[i][j]-1)*9+int(n[i+1]),0) if j==count else dp[i][j]*9
    if int(n[i+1])!=0:
        count+=1
    dp[i+1][K]+=dp[i][K]
    
print(dp[-1][-1])

Submission status: Accepted

Solution code:
N = input()
L = len(N)
K = int(input())
dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(L + 1)]
dp[0][0][1] = 1
for i, x in zip(range(L), map(int, N)):
    for k in range(K):
        dp[i+1][k][0] += dp[i][k][0]  # d == 0
        if x == 0:
            dp[i+1][k][1] += dp[i][k][1]
        elif x > 0:
            dp[i+1][k][0] += dp[i][k][1]
        # d != 0
        for d in range(1, 10):
            dp[i+1][k+1][0] += dp[i][k][0]
            if d == x:
                dp[i+1][k+1][1] += dp[i][k][1]
            elif d < x:
                dp[i+1][k+1][0] += dp[i][k][1]
    dp[i+1][K][0] += dp[i][K][0]  # k == K and d == 0
    if x == 0:
        dp[i+1][K][1] += dp[i][K][1]
    elif x > 0:
        dp[i+1][K][0] += dp[i][K][1]
print(sum(dp[-1][K]))

Submission status: Accepted

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

L = len(str(N))
N2 = list(str(N))
dp1 = [[0 for i in range(L+1)] for j in range(3+1)]
dp2 = [[0 for i in range(L+1)] for j in range(3+1)]
dp1[0]=[1]*(L+1)
temp = 0
for i in range(L):
    #print(temp)
    if (N2[i] != "0" and temp <= K-1):
        temp += 1
        dp2[min(temp,K)][i+1] += 1
    elif (N2[i] == "0" and dp2[min(temp,K)][i] == 1):
        dp2[min(temp,K)][i+1] += 1
#print(dp2)

dp1[1][1] = int(N2[0])-1
for i in range(1,K+1):
    for j in range(2,L+1):
        if (N2[j-1] != "0" and i == 1 ):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 2):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 3):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        else:
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]
#print(dp1)
print(dp1[K][-1]+dp2[K][-1])

Submission status: Accepted

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

dp = [[[0 for a in range(k+1)] for b in range(2)] for c in range(l+5)]

dp[0][0][0] = 1
#print(dp)

for a in range(l) :
    for b in range(2) :
        for c in range(k+1) :
            for d in range(10) :
                na = a
                nb = b
                nc = c
                if b == 0 :
                    if d > int(n[a]) :
                        continue
                    if d < int(n[a]) :
                        nb = 1
                if c == k and d > 0 :
                    continue
                if d != 0 :
                    nc += 1
                #print(a,b,c,na,nb,nc)
                dp[na+1][nb][nc] += dp[a][b][c]

#print(dp[l][0][k])
#print(dp[l][1][k])
print(dp[l][0][k]+dp[l][1][k])

Submission status: Accepted

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

sN=str(N)
keta=len(sN)

#dp[i][j][t]=Nと同じ桁数の整数で上からi桁目までで0でない数字がj個あるものの個数
dp=[[[0]*2 for __ in range(K+1)] for _ in range(keta+1)]
dp[0][0][1]=1

for i in range(keta):
    for j in range(K+1):
        for k in range(2):
            for n in range(10):
                if k==1 and n>int(sN[i]): break
                ni=i+1
                nj=j if n==0 else j+1
                if nj>K: continue
                nk=1 if k==1 and n==int(sN[i]) else 0
                dp[ni][nj][nk]+=dp[i][j][k]

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

Submission status: Accepted

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

dp = [[[0]*2 for _ in range(K+1)] for _ in range(L+1)]
dp[0][0][0] = 1
for i,c in enumerate(N):
    c = int(c)
    for k in range(K+1):
        for less in range(2):
            for d in range(10):
                nk = k + (d>0)
                if nk > K: continue
                if less == 0 and d > c: continue
                nxless = not(less==0 and d==c)
                dp[i+1][nk][nxless] += dp[i][k][less]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:
def f(n, k):
    # dp[ 上からの桁数 ][ N 未満フラグ ][ 0でない数の個数 ] := このパターンの総数
    # dp[i][smaller][j]
    # smaller = 0 のときNに一致
    # smaller = 1 のときN未満
    n = str(n)
    L = len(n)

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

    for i in range(L):
        D = int(n[i])
        for smaller in range(2):
            for j in range(k+1):
                for d in range((9 if smaller else D)+1):
                    dp[i+1][smaller or (d < D)][j + (d != 0)] += dp[i][smaller][j]

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


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

    print(f(N, K))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int):
    n = len(str(N))
    dp = [[[0]*2 for _ in range(5)] for _ in range(n+1)]
    # dp[i][j][k] = 上からi桁みたときに0以外がjこあり確定フラグ(0が未確定)がkをみたす数字の数
    number = str(N)
    dp[0][0][0] = 1

    for i in range(n):
        for j in range(4):
            if number[i] == "0":
                #　未確定から未確定
                dp[i+1][j][0] += dp[i][j][0]

                # 確定から確定
                dp[i+1][j+1][1] += dp[i][j][1]*9
                dp[i+1][j][1] += dp[i][j][1]        

                # 未確定から確定(なし)
            else:
                # 未確定から未確定
                dp[i+1][j+1][0] += dp[i][j][0]

                # 確定から確定
                dp[i+1][j+1][1] += dp[i][j][1]*9
                dp[i+1][j][1] += dp[i][j][1]

                # 未確定から確定
                dp[i+1][j+1][1] += dp[i][j][0]*(int(number[i])-1)
                dp[i+1][j][1] += dp[i][j][0]

    print(sum(dp[n][K]))
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))


# dp[i + 1][smaller][j] = 上からi桁目までで0でない桁がj個ある数字の数
N = input()
K = I()
l = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(l + 1)]
dp[0][False][0] = 1
for i in range(1, l + 1):
    N_i = int(N[i - 1])
    for smaller in [True, False]:  # smaller := Nより小さいことが確定している
        for j in range(K + 1):
            for d in range((9 if smaller else N_i) + 1):
                if j - (0 if d == 0 else 1) >= 0:
                    dp[i][smaller or d < N_i][j] += dp[i - 1][smaller][j - (0 if d == 0 else 1)]

print(dp[l][True][K] + dp[l][False][K])

Submission status: Accepted

Solution code:
# reference https://maspypy.com/atcoder-%e5%8f%82%e5%8a%a0%e6%84%9f%e6%83%b3-2019-02-09abc-154
from functools import lru_cache

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


@lru_cache(None)
def F(N, K):
    # print("NK", N, K)
    """N以下で0でないものがちょうどK個。0を含める"""
    # assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0  # 求める数字は作れない
    q, r = divmod(N, 10)
    # print("qr", q, r)
    ret = 0
    if K >= 1:  # 1 の位が nonzero (1 の位で 0 でない数字 を消費するので、第 2 引数は K - 1)
        ret += F(q, K-1) * r  # smaller than 1 の位
        ret += F(q-1, K-1) * (9-r)  # bigger than 1 の位
    ret += F(q, K)  # 1の位が zero (1 の位で 0 でない数字 を消費していないので、第 2 引数は K)
    return ret


print(F(N, K))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = input()
K = INT()
L = len(n)

# dp[L][k][2]

# k = 0 nと一致
# k = 1 nより小さい
dp = [[[0] * 2 for i in range(4)] for j in range(L+1)]
dp[0][0][0] = 1
for i in range(L):
    for j in range(4):
        for k in range(2):
            nd = int(n[i])
                
            for d in range(10):
                ni = i + 1
                nj = j
                nk = k

                if d != 0:
                    nj += 1
                # 設定してるKよりもnjが大きいならありえない
                if nj > K:
                    continue
                # 今までみたところ一致してたら
                if k == 0:
                    # 見てる数ndよりもdが大きかったら，
                    # それより大きい数字はない
                    if d > nd:
                        continue
                    # 次も同じなら一致してる
                    if d == nd:
                        nk = 0
                    # 違うなら一致してない
                    if d < nd:
                        nk = 1
                # print(ni, nj, nk)
                dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

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

sN=str(N)
keta=len(sN)

#dp[i][j][t]=Nと同じ桁数の整数で上からi桁目までで0でない数字がj個あるものの個数
dp=[[[0]*2 for __ in range(K+1)] for _ in range(keta+1)]
dp[0][0][1]=1

for i in range(1,keta+1):
    for j in range(K+1):
        if sN[i-1]=='0':
            dp[i][j][1] = dp[i-1][j][1]
        elif j>0:
            dp[i][j][1] = dp[i-1][j-1][1]
        dp[i][j][0] = dp[i-1][j][0]
        if sN[i-1]!='0':
            dp[i][j][0] += dp[i-1][j][1]
        if j>0:
            dp[i][j][0] += dp[i-1][j-1][1]*(max(0,int(sN[i-1])-1))
            dp[i][j][0] += dp[i-1][j-1][0]*9

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

Submission status: Accepted

Solution code:
NN = 2020202
MOD = 10**9+7
INF = float("inf")

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

dp0 = [[0] * 4 for _ in range(len_n)]  # not fixed
dp1 = [[0] * 4 for _ in range(len_n)]  # fixed
dp0[0][1] = 1
dp1[0][1] = int(N[0]) - 1
for i in range(len_n):
    dp1[i][0] = 1

for i in range(1, len_n):
    cur = int(N[i])
    for k in range(1, 4):
        if cur == 0:
            dp0[i][k] = dp0[i - 1][k]
            dp1[i][k] = dp1[i - 1][k] + 9*dp1[i - 1][k-1]

        else:
            dp0[i][k] = dp0[i - 1][k - 1]
            dp1[i][k] = dp1[i - 1][k] + 9*dp1[i - 1][k-1] + (cur - 1)*dp0[i - 1][k-1] + dp0[i - 1][k]

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

Submission status: Accepted

Solution code:
n = int(input())

k = int(input())

keta = len(str(n))

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

s = str(n)

#dp[何桁目か][未満フラグ 0 = 未満][ゼロ以外のの個数]

x = int(s[0])
if x == 1:
    dp[0][1][0] = 1
else:
    dp[0][1][0] += 1
    dp[0][0][0] += x - 1


for index, c in enumerate(s[1:]):
    i = index + 1
    x = int(c)
    dp[i][0][0] += 9
    for j in range(k+1):
        dp[i][0][j] += dp[i - 1][0][j]
        if x == 0:
            dp[i][1][j] += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
        elif x:
            dp[i][1][j + 1] += dp[i - 1][1][j]
            dp[i][0][j]     += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
            dp[i][0][j + 1] += dp[i - 1][1][j] * (x - 1)
    # print(sum(dp[i][0]) + sum(dp[i][1]))
    # print(s[:index + 2])
    # print(dp)




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

Submission status: Accepted

Solution code:
n = int(input())

k = int(input())

keta = len(str(n))

dp = [[[0 for j in range(keta+2)] for _ in range(2)]  for i in range(keta)]

s = str(n)

#dp[何桁目か][未満フラグ 0 = 未満][ゼロ以外のの個数]

x = int(s[0])
if x == 1:
    dp[0][1][0] = 1
else:
    dp[0][1][0] += 1
    dp[0][0][0] += x - 1


for index, c in enumerate(s[1:]):
    i = index + 1
    x = int(c)
    dp[i][0][0] += 9
    for j in range(k+1):
        dp[i][0][j] += dp[i - 1][0][j]
        if x == 0:
            dp[i][1][j] += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
        elif x:
            dp[i][1][j + 1] += dp[i - 1][1][j]
            dp[i][0][j]     += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
            dp[i][0][j + 1] += dp[i - 1][1][j] * (x - 1)
    # print(sum(dp[i][0]) + sum(dp[i][1]))
    # print(s[:index + 2])
    # print(dp)




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

Submission status: Accepted

Solution code:
n = int(input())

k = int(input())

keta = len(str(n))

dp = [[[0 for j in range(keta+2)] for _ in range(2)]  for i in range(keta)]

s = str(n)

#dp[何桁目か][未満フラグ 0 = 未満][ゼロ以外のの個数]

x = int(s[0])
if x == 1:
    dp[0][1][0] = 1
else:
    dp[0][1][0] += 1
    dp[0][0][0] += x - 1


for index, c in enumerate(s[1:]):
    i = index + 1
    x = int(c)
    dp[i][0][0] += 9
    for j in range(keta+1):
        dp[i][0][j] += dp[i - 1][0][j]
        if x == 0:
            dp[i][1][j] += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
        elif x:
            dp[i][1][j + 1] += dp[i - 1][1][j]
            dp[i][0][j]     += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
            dp[i][0][j + 1] += dp[i - 1][1][j] * (x - 1)
    # print(sum(dp[i][0]) + sum(dp[i][1]))
    # print(s[:index + 2])
    # print(dp)




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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = input()
K = INT()

dp_co = [[0 for _ in range(3 + 1)] for _ in range(len(N) + 1)]
dp_unco = [[0 for _ in range(3 + 1)] for _ in range(len(N) + 1)]
dp_co[0][0] = 1

for i in range(len(N)):
	for j in range(4):
		for k in range(2):
			for num in range(10):
				n_i, n_j, n_k = i + 1, j, k
				if num != 0:
					n_j += 1
				if n_j > K:
					continue
				if k == 0:
					if num > int(N[i]):
						continue
					if num == int(N[i]):
						k = 0
					if num < int(N[i]):
						n_k = 1
				if n_k == 0:
					dp_co[n_i][n_j] += dp_co[i][j]
				if n_k == 1:
					if k == 0:
						dp_unco[n_i][n_j] += dp_co[i][j]
					else:
						dp_unco[n_i][n_j] += dp_unco[i][j]						

ans = dp_co[len(N)][K] + dp_unco[len(N)][K]
print(ans)

Submission status: Accepted

Solution code:
#再帰ver

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

from collections import defaultdict
dd = defaultdict(int)


#NN以下，KKが非zero要素を残り使っても良い回数
def rep(NN,KK):
    if KK<0:
        return 0
    
    ha=NN*10+KK
    if dd[ha]!=0:
        return dd[ha]
    
    if NN<0:
        return 0
    
    if NN==0:
        if KK==0:
            return 1
        return 0
        
    
    na=NN//10
    nb=NN%10
    if nb==0:
        dd[ha]=rep(na,KK)+rep(na-1,KK-1)*9
        return dd[ha]
    else:
        dd[ha]=rep(na,KK)+rep(na,KK-1)*nb+rep(na-1,KK-1)*(9-nb)
        return dd[ha]
    
print(rep(N,K))

Submission status: Accepted

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

def c(n,k):
	if 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
def f(N, K):
	if N == 0 and K > 0:
		return 0

	if K == 0:
		return 1
	digit = len(str(N))
	ret = 0
	if digit > K:
		ret += c(digit-1, K) * (9 ** K)
	a = 10**(digit-1)
	d = N // a
	ret += (d-1) * c(digit-1, K-1) * (9 ** (K-1))
	ret += f(N - d*a, K-1)

	return ret

print(f(N,K))

Submission status: Accepted

Solution code:

def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

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

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            #print(result)
            result %= (10**9+7)

    return result


def f(x,k,small):    
    d = len(x)
    #print(x, k, d,small)
    if d == 0:        
        if k==0:
            return 1
        else:   
            return 0
    #if d==1 and k==0:
    #    return 0 
    if d<k:
        return 0

    if k==0:
        return 1

    #if d==1:
    #    return x[0]

    if small:
        #print(k,d)
        return (9**(k))*cmb(d, k)

    #A = max(x[0]-1, 0)
    if x[0]==0:
        return f(x[1:],k,False)
    zero = f(x[1:],k,True)
    aida=f(x[1:],k-1,True)*(x[0]-1)
    eq = f(x[1:], k-1,False)
    #print(zero,aida,eq)
    return zero+aida+eq

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

print(f(N,K,False))

#dp0[i][j]=x[0]*dp0[i][j]+dp1[i+1][j]

Submission status: Accepted

Solution code:
Nstr=input()
N=int(Nstr)
K=int(input())
x=len(Nstr)
dp0=[[0]*(K+1) for i in range(x+1)]
dp1=[[0]*(K+1) for i in range(x+1)]

dp1[0][0]=1

for i in range(1,x+1):
  dp0[i][0]=dp0[i-1][0]+dp1[i-1][0]
  for j in range(1,K+1):
    if Nstr[i-1]!='0':
      dp1[i][j]=dp1[i-1][j-1]
      dp0[i][j]+=(dp1[i-1][j-1]*(int(Nstr[i-1])-1)+dp1[i-1][j])
    else:
      dp1[i][j]=dp1[i-1][j]
    dp0[i][j]+=(dp0[i-1][j]+dp0[i-1][j-1]*9)

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

Submission status: Accepted

Solution code:
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):
    N=int(n[i-1])
    for j in range(k+1):
        DP[i][1][j] +=DP[i-1][1][j]
        if N!=0:DP[i][1][j] +=DP[i-1][0][j]
        else:DP[i][0][j] +=DP[i-1][0][j]
        if j!=0:
            DP[i][1][j] +=9*DP[i-1][1][j-1]
            if N!=0:
                DP[i][0][j] +=DP[i-1][0][j-1]
                DP[i][1][j] +=(N-1)*DP[i-1][0][j-1]

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

Submission status: Accepted

Solution code:
s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for a in range(n):
  for b in range(k + 1):
    for c in range(2):
      nd = int(s[a])
      for d in range(10):
        na, nb, nc = a + 1, b, c
        if d != 0:
          nb += 1
        if nb > k:
          break
        if 0 == nc:
          if d > nd:
            break
          if d < nd:
            nc += 1
        dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:
s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if 0 != d:
                    nb += 1
                if nb > k:
                    break
                if 0 == c:
                    if d > nd:
                        break
                    elif d < nd:
                        nc = 1
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:
s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if 0 != d:
                    nb += 1
                if nb > k:
                    continue
                if nc == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nc = 1
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
from functools import lru_cache

@lru_cache(maxsize=100000000000)
def dp(n, k): #0以上n以下の数で０でない数字がちょうどk個あるもの。
  if k == 0:
    return 1
  elif n == 0:
    return 0
  else:
    n = int(n)
    s = str(n)
    digit = len(s)
    m, fdigit = divmod(n,10)
    if m >= 1:
        return int(dp(m, k-1) * fdigit + dp(m-1, k-1)* (9-fdigit) + dp(m, k))
    elif k == 1:
        return n
    elif k == 2 or k == 3:
        return 0
    else:
        return 1
if K == 0:
    answer = dp(N, K)-1
else:
    answer = dp(N, K)
print(int(answer))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = rs()
    K = ri()
    a = [int(c) for c in N]
    dp = [[0] * (K + 1) for i in range(2)]

    dp[1][0] = 1
    dp[1][1] = a[0] - 1
    dp[0][1] = 1

    for i in range(1,len(a)):
        ndp = [[0] * (K + 1) for i in range(2)]

        for k in range(K+1):
            if k + 1 <= K:
                ndp[1][k + 1] += 9 * dp[1][k] # 1 ~ 9
            ndp[1][k] += dp[1][k] # 0
        
        for k in range(K+1):
            if a[i] == 0:
                ndp[0][k] += dp[0][k] #0
            else:
                ndp[1][k] += dp[0][k] #0
                if k + 1 <= K:
                    ndp[1][k + 1] += (a[i] - 1) * dp[0][k] # 1 ~ (a[i]-1)
                    ndp[0][k + 1] += dp[0][k]
        
        dp = ndp
    print(dp[0][K] + dp[1][K])
    


if __name__ == "__main__":
    main()