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:
#e digitDP    
n = int(input())
k = int(input())
s=str(n)
l=len(s)

dp = [[[0]*(3+1) for _ in range(2)] for _ in range(l) ]
#dp[i桁目][0=未満確定、1=不確定][0以外の数字の数]
x = int(s[0])
#未満確定、1以上0個 =0
dp[0][0][0] = 1
#未満確定、1以上1個 = 1 ~ x-1
dp[0][0][1] = x-1
#head、1以上0個
dp[0][1][0] = 0
#head、1以上1個 = x
dp[0][1][1] = 1


for i in range(1,l):
    x = int(s[i])
    if x>=1:
        #headじゃない、1以上０こ(0, )
        dp[i][0][0] = dp[i-1][0][0]*1 +dp[i-1][1][0]*1
        #head 1以上0個()
        dp[i][1][0] = dp[i-1][0][0]*0 +dp[i-1][1][0]*0
        for j in [1,2,3]:
            dp[i][0][j] = dp[i-1][0][j-1]*9 +dp[i-1][1][j-1]*(x-1) +dp[i-1][0][j]*1 +dp[i-1][1][j]*1
            dp[i][1][j] = dp[i-1][0][j-1]*0 +dp[i-1][1][j-1]*1     +dp[i-1][0][j]*0 +dp[i-1][1][j]*0
    else:
        #headじゃない、1以上が０こ(0, )
        dp[i][0][0] = dp[i-1][0][0]*1 +dp[i-1][1][0]*0
        #head 1以上0個
        dp[i][1][0] = dp[i-1][0][0]*0 +dp[i-1][1][0]*1
        for j in [1,2,3]:
            dp[i][0][j] = dp[i-1][0][j-1]*9 +dp[i-1][1][j-1]*0 +dp[i-1][0][j]*1 +dp[i-1][1][j]*0
            dp[i][1][j] = dp[i-1][0][j-1]*0 +dp[i-1][1][j-1]*0 +dp[i-1][0][j]*0 +dp[i-1][1][j]*1
            
print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Accepted

Solution code:
from functools import lru_cache
n=int(input())
k=int(input())
@lru_cache(None)
def cal(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+=cal(q,k-1)*r
    ret+=cal(q-1,k-1)*(9-r)
  ret+=cal(q,k)
  return ret

print(cal(n,k))

Submission status: Accepted

Solution code:
import math
import pprint
#N以下の0以外のK種類の数が含まれている数字列
N = int(input())
K = int(input())


N_d = int(math.log10(N))


def N_n(n):
    return int(N//(10**(n))%(10))

dp = [[[-1]*2 for i in range(K+2)] for i in range(int(math.log10(N))+2)]




def rec(i,j,t):
    if j < 0 :
        return 0

    if dp[i][j][t]!=-1:
        return dp[i][j][t]
    
    nnn = N_n(i)
    #print("start",i,j,t, nnn)
    if i == 0:
        if j == 0:
            dp[i][j][t] = 1
        elif j == 1:
            if t:
                dp[i][j][t] = nnn
            else:
                dp[i][j][t] = 9
        else:
            dp[i][j][t] = 0
    else:
        if t:
            if nnn==0:
                dp[i][j][t] = rec(i-1,j,True)
            else:
                dp[i][j][t] = rec(i-1,j,False) + (rec(i-1,j-1,False) * (nnn-1)) + (rec(i-1,j-1,True))
        else:
            dp[i][j][t] = rec(i-1,j,False) + (rec(i-1,j-1,False) * 9)
    return dp[i][j][t]

print(rec(N_d,K,True))
#pprint.pprint(dp)

Submission status: Accepted

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

# 上の桁からDP
# 大きさが微妙な場合は分ける
# dp[桁][0の個数]

def solve(n, k):
    if k == 0:
        return 1
    if n == []:
        return 0
    dp = [[0 for _ in range(k+1)] for _ in range(len(n))]
    dp[0][0] = 1
    dp[0][1] = n[0] - 1
    for i in range(len(n) - 1):
        for j in range(k + 1):
            if j == 0:
                dp[i+1][0] = dp[i][0]
            else:
                dp[i+1][j] = dp[i][j-1] * 9 + dp[i][j]
    # first non-0
    i = 1
    while i < len(n) and n[i] == 0:
        i += 1
    return dp[len(n) - 1][k] + solve(n[i:], k-1)

print(solve(n, k))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc154/tasks/abc154_e

def oneNum(N):
    answer = 0

    while(N > 0):
        if(N >= 9):
            answer = answer + 9
        else:
            answer = answer + N
        
        N = N // 10

    return answer

def twoNum(N):
    answer = 0

    strN = str(N)
    topN = int(strN[0])
    lenN = len(strN)

    if(lenN != 1):
        answer = answer + oneNum(int(strN[1:])) + (topN - 1) * oneNum(int('9' * (lenN - 1)))
        N = int('9' * (lenN - 1))

    while(N >= 10):
        N = N // 10
        answer = answer + 9 * oneNum(N)

    return answer

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

    answer = 0

    if(K == 1):
        answer = oneNum(N)

    elif(K == 2):
        answer = twoNum(N)

    else:
        strN = str(N)
        topN = int(strN[0])
        lenN = len(strN)

        answer = answer + twoNum(int(strN[1:])) + (topN - 1) * twoNum(int('9' * (lenN - 1)))

        N = int('9' * (lenN - 1))

        while(N >= 100):
            N = N // 10
            answer = answer + 9 * twoNum(N)

    print(answer)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
N_digit = len(str(N))
K = int(input())
ans = 0
factorial = [1, 1]
for i in range(2, 101):
    factorial.append(factorial[-1] * i)


def nCr(n, r):
    if n - r < 0:
        return 0
    return factorial[n] // (factorial[r] * factorial[n - r])


if K == 1:
    ans += 9 * (nCr(N_digit - 1, 1))  # 1桁目を0に固定、2桁目以降は自由
    ans += int(str(N)[0])  # 1桁目を考える。2桁目以降は0

elif K == 2:
    ans += (9 ** 2) * (nCr(N_digit - 1, 2))  # 1桁目を0に固定、2桁目以降から自由に2つ
    ans += (int(str(N)[0]) - 1) * 9 * (nCr(N_digit - 1, 1))  # 1桁目を0でなく、かつN以下が確定するように固定
    for d2_position in range(1, N_digit):  # 2つめの0でない数をどこに置くか
        for d2_value in range(1, 10):  # 2つめの0でない数を何にするか
            # 数をつくる
            S = ['0'] * N_digit
            S[0] = str(N)[0]
            S[d2_position] = d2_value
            S = int(''.join(map(str, S)))

            ans += (S <= N)

elif K == 3:
    ans += (9 ** 3) * (nCr(N_digit - 1, 3))  # 1桁目を0に固定、2桁目以降から自由に3つ
    ans += (int(str(N)[0]) - 1) * (9 ** 2) * (nCr(N_digit - 1, 2))  # 1桁目を0でなく、かつN以下が確定するように固定
    for d2_position in range(1, N_digit):  # 2つめの0でない数をどこに置くか
        for d3_position in range(d2_position + 1, N_digit):  # 3つめの0でない数をどこに置くか
            for d2_value in range(1, 10):  # 2つめの0でない数を何にするか
                for d3_value in range(1, 10):  # 3つめの0でない数を何にするか
                    # 数を作る
                    S = ['0'] * N_digit
                    S[0] = str(N)[0]
                    S[d2_position] = str(d2_value)
                    S[d3_position] = str(d3_value)
                    S = int(''.join(S))

                    ans += (S <= N)

print(ans)

Submission status: Accepted

Solution code:
def comb(a, b):
    if (a < b) or (a < 0) or (b < 0):
        return 0
    res = 1
    for i in range(b):
        res *= a - i
        res //= i + 1
    return res

def solve(n, k):
    s = str(n)
    d = len(s)
    def f(i, t, ok):
        if ok:
            return comb(d-i, t) * (9**t)
        elif t == 0:
            return 1
        elif i == d:
            return 0
        if s[i] == "0":
            return f(i+1, t, False)
        res = f(i+1, t, True)
        if t > 0:
            for j in range(1, 10):
                if int(s[i]) > j:
                    res += f(i+1, t-1, True)
                elif int(s[i]) == j:
                    res += f(i+1, t-1, False)
                else:
                    break
        return res
    return f(0, k, False)

n = int(input())
k = int(input())
print(solve(n, k))

Submission status: Accepted

Solution code:
n = int(input())
k = int(input())
l = len(str(n))
a = [int(str(n)[i]) for i in range(l)]

dp = [[[0, 0] for _ in range(k + 1)] for _ in range(l)] #dp[i桁目][0でないのがj個][0: 未満, 1: 未満不確定]

dp[0][0][0] = 1         #0桁目で0でないのが0個、未満確定は0が入る1個
dp[0][0][1] = 0         #0桁目で0でないのが0個、未満不確定はa[0]!=0より0個
dp[0][1][0] = a[0] - 1  #0桁目で0でないのが1個、未満確定は1-a[0]-1のa[0]-1個
dp[0][1][1] = 1         #0桁目で0でないのが1個、未満不確定はa[0]の1個

#print(a)

for i in range(1, l):
    for j in range(k + 1):
        if j > 0 and a[i] != 0:
            #未満確定で0以外がj個のとき、0の1個
            #未満確定で0以外がj-1個のとき、1-9の9個
            #未満不確定で0以外がj個のとき、0の1個
            #未満不確定で0以外がj-1個のとき、1-a[i]-1のa[i]-1個
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j-1][0] * 9 \
                        + dp[i-1][j][1] * 1 \
                        + dp[i-1][j-1][1] * (a[i] - 1)
            #未満不確定で0以外がj-1個のとき、a[i]の1個
            dp[i][j][1] = dp[i-1][j-1][1] * 1

        elif j > 0 and a[i] == 0:
            #未満確定で0以外がj個のとき、0の1個
            #未満確定で0以外がj-1個のとき、1-9の9個
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j-1][0] * 9
            #未満確定で0以外がj個のとき、0の1個
            dp[i][j][1] = dp[i-1][j][1] * 1
        
        elif j == 0 and a[i] != 0:
            #未満確定で0以外がj個のとき、0の1個
            #未満不確定で0以外がj個のとき、0の1個
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j][1] * 1
            #a[i] == 0のとき未満不確定はありえない
            dp[i][j][1] = 0
        elif j == 0 and a[i] == 0:
            #未満確定で0以外がj個のとき、0の1個
            dp[i][j][0] = dp[i-1][j][0] * 1
            #未満不確定で0以外がj個のとき、0==a[i]の1個
            dp[i][j][1] = dp[i-1][j][1] * 1
            

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

Submission status: Accepted

Solution code:

'''
import math
n = int(input())
k = int(input())
b = len(str(n)) #桁数

ans = 0

for i in range(k, b + 1):
    in0 = i - 1 #0が入る可能性のあるところの桁数
    if in0 > 0:
        #print(in0, k - 1, in0 - k + 1)
        a = math.factorial(in0) // math.factorial(k - 1) // math.factorial(in0 - k + 1)
        ans += 9 * pow(9, k - 1)
        #print(9 * pow(9, a))
        print('a', 9 * pow(9, k - 1))
    else:
        ans += pow(9, i)
        print('b', pow(9, i))

print(ans)

for i in range(n + 1, pow(10, b)):
    #print(i)
    num = str(i)
    cnt = 0
    for j in range(b):
        if num[j] == '0':
            cnt += 1
    if cnt == b - k:
        ans -= 1
        #print(i, ans)
'''
'''
b = len(str(n)) #桁数
if b > k:
    a = math.factorial(b - 1) // math.factorial(k) // math.factorial(b - 1 - k)
    ans = a * pow(9, k)
else: 
    ans = 0

if k == 1:
    ans += int(str(n)[0])
elif k == 2:
    c = int(str(n)[0])
    for i in range(1, b): #2つめの1-9が入る場所
        for j in range(1, c + 1): #1つめの1-9の数字
            if j < c or i > 1:
                ans += 9
            else:
                #print(i, j, int(str(n)[i]))
                ans += int(str(n)[i])
else:
    c = [int(str(n)[i]) for i in range(b)] #桁数分離
    d = 1 #初めて0以外の数字が出てくる桁
    for i in range(1, b):
        if c[i] == 0:
            d += 1
        else:
            break
    if d < b: #n0000000とかでないとき
        ans += (c[0] - 1) * 81 * math.factorial(b - 1) // math.factorial(2) // math.factorial(b - 3) #1つめの数字がc[0]より小さい
        if b - d > 2:
            ans += 81 * math.factorial(b - d - 1) // math.factorial(2) // math.factorial(b - d - 3) #1つめの数字が一緒で2つめの数字の位置が低い場合
        ans += (c[d] - 1) * 9 * (b - d - 1) #1つめの数字が一緒で2つめの数字の位置が一緒で値が小さいとき
        #print(ans)
        #1つめと2つめの数字が一緒のとき
        for i in range(d + 1, b): #3つめの数字の位置
            for j in range(1, 10): #3つめの数字の値
                e = ['0' for _ in range(b)]
                e[0] = c[0]
                e[d] = c[d]
                e[i] = j
                f = ''
                for k in range(b):
                    f += str(e[k])
                f = int(f)
                if f <= n:
                    ans += 1






print(ans)
'''

'''
n = int(input())
k = int(input())
l = len(str(n))

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

for i in range(l):
    for j in range(k + 1):
        for m in range(2):
            d = int(str(n)[i])

            for nextd in range(10):
                nextj = j
                nextm = m

                if nextd != 0:
                    nextj += 1
                if nextj > k:
                    continue
                
                if m == 0:
                    if d < nextd:
                        continue
                    elif nextd < d:
                        nextm = 1
                
                dp[i + 1][nextj][nextm] += dp[i][j][m]

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

n = int(input())
k = int(input())
l = len(str(n))
a = [int(str(n)[i]) for i in range(l)]

dp = [[[0, 0] for _ in range(k + 1)] for _ in range(l)] #dp[i桁目][0でないのがj個][0: 未満, 1: 未満不確定]

dp[0][0][0] = 1         #0桁目で0でないのが0個、未満確定は0が入る1個
dp[0][0][1] = 0         #0桁目で0でないのが0個、未満不確定はa[0]!=0より0個
dp[0][1][0] = a[0] - 1  #0桁目で0でないのが1個、未満確定は1-a[0]-1のa[0]-1個
dp[0][1][1] = 1         #0桁目で0でないのが1個、未満不確定はa[0]の1個

#print(a)

for i in range(1, l):
    for j in range(k + 1):
        if j > 0 and a[i] != 0:
            #未満確定で0以外がj個のとき、0の1個
            #未満確定で0以外がj-1個のとき、1-9の9個
            #未満不確定で0以外がj個のとき、0の1個
            #未満不確定で0以外がj-1個のとき、1-a[i]-1のa[i]-1個
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j-1][0] * 9 \
                        + dp[i-1][j][1] * 1 \
                        + dp[i-1][j-1][1] * (a[i] - 1)
            #未満不確定で0以外がj-1個のとき、a[i]の1個
            dp[i][j][1] = dp[i-1][j-1][1] * 1

        elif j > 0 and a[i] == 0:
            #未満確定で0以外がj個のとき、0の1個
            #未満確定で0以外がj-1個のとき、1-9の9個
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j-1][0] * 9
            #未満確定で0以外がj個のとき、0の1個
            dp[i][j][1] = dp[i-1][j][1] * 1
        
        elif j == 0 and a[i] != 0:
            #未満確定で0以外がj個のとき、0の1個
            #未満不確定で0以外がj個のとき、0の1個
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j][1] * 1
            #a[i] == 0のとき未満不確定はありえない
            dp[i][j][1] = 0
        elif j == 0 and a[i] == 0:
            #未満確定で0以外がj個のとき、0の1個
            dp[i][j][0] = dp[i-1][j][0] * 1
            #未満不確定で0以外がj個のとき、0==a[i]の1個
            dp[i][j][1] = dp[i-1][j][1] * 1
            

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

Submission status: Accepted

Solution code:
n = input()
km = int(input())
dp1 = [[0] * (4) for _ in range(len(n) + 1)]
dp2 = [[0] * (4) for _ in range(len(n) + 1)]
dp1[0][0] = 1
for i in range(len(n)):
    for j in range(4):
        if n[i] == '0':
            dp1[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        else:
            dp2[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        if j < 3:
            for k in range(1, ord(n[i]) - ord('0')):
                dp2[i + 1][j + 1] += dp1[i][j]
            if n[i] != '0':
                dp1[i + 1][j + 1] += dp1[i][j]
            for k in range(1, 10):
                dp2[i + 1][j + 1] += dp2[i][j]
print(dp1[len(n)][km] + dp2[len(n)][km])

Submission status: Accepted

Solution code:
n = input()
km = int(input())
dp1 = [[0] * (4) for _ in range(len(n) + 1)]
dp2 = [[0] * (4) for _ in range(len(n) + 1)]
dp1[0][0] = 1
for i in range(len(n)):
    for j in range(4):
        # i+1桁目に0が入る場合
        if n[i] == '0':
            dp1[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        else:
            dp2[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        if j < 3:
            for k in range(1, ord(n[i]) - ord('0')):
                dp2[i + 1][j + 1] += dp1[i][j]
            if n[i] != '0':
                dp1[i + 1][j + 1] += dp1[i][j]
            for k in range(1, 10):
                dp2[i + 1][j + 1] += dp2[i][j]
print(dp1[len(n)][km] + dp2[len(n)][km])

Submission status: Accepted

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

S=str(N)
l=len(S)

dp=[[[0]*4 for __ in range(2)] for _ in range(l)]
dp[0][0][1]=1
dp[0][1][0]=1
dp[0][1][1]=int(S[0])-1

for i in range(1, l):
  if S[i]=='0':
    for k in range(1, 4):
      dp[i][0][k]=dp[i-1][0][k]
      dp[i][1][k]=dp[i-1][1][k]+dp[i-1][1][k-1]*9
    dp[i][1][0]=dp[i-1][1][0]
  else:
    dp[i][0][2]=dp[i-1][0][1]
    dp[i][0][3]=dp[i-1][0][2]
    dp[i][1][0]=1
    dp[i][1][1]=dp[i-1][1][1]+dp[i-1][1][0]*9+dp[i-1][0][1]
    dp[i][1][2]=dp[i-1][1][2]+dp[i-1][1][1]*9+dp[i-1][0][2]+dp[i-1][0][1]*(int(S[i])-1)
    dp[i][1][3]=dp[i-1][1][3]+dp[i-1][1][2]*9+dp[i-1][0][3]+dp[i-1][0][2]*(int(S[i])-1)
    
print(dp[-1][0][K]+dp[-1][1][K])

Submission status: Accepted

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

keta = len(n)

# dp0 = ヨユーなやつ, dp1 = ギリなやつ
dp0 = [[0 for j in range(keta+1)] for i in range(keta+1)]
dp1 = [[0 for j in range(keta+1)] for i in range(keta+1)]

dp1[0][0] = 1

for i in range(keta):
    for j in range(keta+1):
        # ギリギリのやつ(dp1)の処理
        if n[i] == '0': # i+1桁目が0の場合
            dp1[i+1][j] = dp1[i][j] # 真上からスライド
        else: # i+1桁目が1~9の場合
            if j < keta:
                dp1[i+1][j+1] = dp1[i][j] # 左上からスライド
        
        # ヨユーなやつ(dp0)の処理
        if n[i] == '0': # i+1桁目が0の場合
            # i桁目がヨユーな状態ではi+1桁目には何でも入れられる
            dp0[i+1][j] += dp0[i][j] # i+1桁目に0を入れた場合
            if j < keta:
                dp0[i+1][j+1] += dp0[i][j] * 9 # i+1桁目に1~9を入れた場合
            # i桁目までギリだったときの、i+1桁目のヨユーなやつのカウント
                # 何もない(ギリである0しか入れられないため)
        else: # i+1桁目が1~9の場合
            # i桁目がヨユーな状態ではi+1桁目には何でも入れられる
            dp0[i+1][j] += dp0[i][j] # i+1桁目に0を入れた場合
            if j < keta:
                dp0[i+1][j+1] += dp0[i][j] * 9 # i+1桁目に1~9を入れた場合
            # i桁目までギリだったときの、i+1桁目のヨユーなやつのカウント
            dp0[i+1][j] += dp1[i][j] # i+1桁目に0を入れた場合
            if j < keta:
                dp0[i+1][j+1] += dp1[i][j] * (ord(n[i])-ord('0')-1) # i+1桁目にrange(1, n[i])を入れた場合

if k > keta:
    print(0)
else:
    print(dp0[keta][k] + dp1[keta][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):
    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])

Submission status: Accepted

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

def main():
    n = input().rstrip()
    k = int(input())
    dp = [[[0 for equal_n      in range(2)]
              for cnt_not_zero in range(k + 1)]
              for digit        in range(len(n) + 1)]
    dp[0][0][1] = 1
    for digit in range(len(n)):#桁
        for cnt_not_zero in range(k+1):#非0の個数
            for equal_n in reversed(range(2)):#nと一致しているかn未満か
                std_val = int(n[digit])
                for target_val in range(10):
                    target_digit = digit + 1
                    target_cnt_not_zero = cnt_not_zero
                    if target_val != 0:
                        target_cnt_not_zero += 1
                    if target_cnt_not_zero > k:
                        continue
                    target_equal_n = equal_n
                    if equal_n == 1:
                        if target_val > std_val:
                            continue
                        if target_val < std_val:
                            target_equal_n = 0
                    dp[target_digit][target_cnt_not_zero][target_equal_n] += dp[digit][cnt_not_zero][equal_n]
    print(dp[len(n)][k][1] + dp[len(n)][k][0])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    n = input().rstrip()
    k = int(input())
    dp = [[[0 for l in range(2)] for j in range(k + 1)] for i in range(len(n) + 1)]
    dp[0][0][0] = 1
    for i in range(len(n)):
        for j in range(k+1):
            for l in range(2):
                x = int(n[i])
                for d in range(10):
                    n_i = i+1
                    n_j = j
                    n_l = l
                    if d != 0:
                        n_j += 1
                    if n_j > k:
                        continue
                    if l == 0:
                        if d > x:
                            continue
                        if d < x:
                            n_l = 1
                    dp[n_i][n_j][n_l] += dp[i][j][l]
    print(dp[len(n)][k][0] + dp[len(n)][k][1])

if __name__ == '__main__':
    main()

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 nc == 0:
                    if d < nd:
                        nc = 1
                    if d > nd:
                        break
                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 d != 0:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if d < nd:
                        nc = 1
                    if d > nd:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np
from functools import lru_cache

def main():
	n=int(input())
	k=int(input())
	
	@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))
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
s = input()
k = int(input())
n = len(s)
dp = [[[0] * (k + 1) for i in range(2)] for i in range(n + 1)]
dp[0][0][0] = 1

# dp[i][j][k] i:桁数 j:smallフラグ 1はsmall確定、0はsと同じ値 k:ゼロ以外の数字を使った回数
for i in range(n):
    for j in range(2):
        for l in range(k + 1): #lはK+1(つまりk)までの範囲にしても問題なし。下でl<kするから
            c = int(s[i])
            if j == 1:  # small確定の場合
                dp[i + 1][j][l] += dp[i][j][l]  # 0
                if l < k:  # まだ使えるなら、   ※比較する変数注意！
                    dp[i + 1][j][l + 1] += dp[i][j][l] * 9  # 1~9を使う
            else:  # j==0のとき
                if c == 0:
                    # cが0のときは0しか選べなく、small確定できない
                    dp[i + 1][0][l] += dp[i][j][l]
                else:
                    dp[i + 1][1][l] += dp[i][j][l]  # Cより小さい0を使う→small確定
                    if l < k: #※比較する変数注意！
                        dp[i + 1][1][l + 1] += dp[i][j][l] * \
                            (c - 1)  # c以外の数字を使う、small確定
                        dp[i + 1][0][l + 1] += dp[i][j][l]  # cを使う、small確定できない
print(dp[n][1][k]+dp[n][0][k])

Submission status: Accepted

Solution code:
from itertools import product
n = input()
k = int(input())
dp = [[[0] * (k + 2) for _ in range(2)] for _ in range(len(n) + 1)]
dp[0][0][0] = 1
for i, j, l in product(range(len(n)), range(2), range(k + 1)):
    for x in range(10):
        if j == 0 and x > int(n[i]):
            continue
        dp[i + 1][0 if j == 0 and x == int(n[i]) else 1][l + 1 if x != 0 else l] += dp[i][j][l]
print(dp[len(n)][0][k] + dp[len(n)][1][k])

Submission status: Accepted

Solution code:
S = str(input())
K = int(input())
dp = [[[0, 0] for _ in range(4)] for _ in range(105)]
dp[0][0][0] = 1
# iは桁
# jはこれまでの非0の数
# kはNより小さいことが確定しているか否か

for i in range(len(S)):
	nxt_d = int(S[i])
	for j in range(4):
		for k in range(2):
			# 次入る数字を探す（判定）
			for d in range(10):
				nxt_i = i + 1
				nxt_j = j
				nxt_k = k
				if d != 0: # 非0の場合
					nxt_j += 1
				if nxt_j > K: # 非0の数が制限を超えちゃった
					continue
				if k == 0: # Nより小さいことが確定していない
					if d > nxt_d: continue
					if d < nxt_d: nxt_k = 1
				dp[nxt_i][nxt_j][nxt_k] += dp[i][j][k]
ans = dp[len(S)][K][0] + dp[len(S)][K][1]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
N = len(str(n))
k = int(input())
s = [int(i) for i in str(n)]
dpi = [[0]*(k+1) for _ in range(N+1)]
dpj = [[0]*(k+1) for _ in range(N+1)]
dpi[0][0] = 1
for i in range(N):
    for j in range(k+1):
        dpi[i+1][j] += dpi[i][j]*(s[i]==0)
        dpj[i+1][j] += dpj[i][j]+dpi[i][j]*(s[i]>0)
        if j < k:
            dpi[i+1][j+1]+=dpi[i][j]*(s[i]>0)
            dpj[i+1][j+1]+=dpj[i][j]*9+dpi[i][j]*max(0,s[i]-1)
print(dpi[N][k]+dpj[N][k])

Submission status: Accepted

Solution code:
import sys
import math
import itertools

nums = list(map(int, list(input())))
k = int(input())

dp0 = [[0 for _ in range(3)] for _ in range(len(nums))]
dp1 = [[0 for _ in range(3)] for _ in range(len(nums))]

dp0[0][0] = nums[0] - 1
dp1[0][0] = 1

for i in range(1, len(nums)):
	if nums[i] > 0:
		dp0[i][0] = dp0[i - 1][0] + dp1[i - 1][0] + 9
		dp0[i][1] = dp0[i - 1][1] + dp1[i - 1][1] + dp0[i - 1][0] * 9 + dp1[i - 1][0] * (nums[i] - 1)
		dp0[i][2] = dp0[i - 1][2] + dp1[i - 1][2] + dp0[i - 1][1] * 9 + dp1[i - 1][1] * (nums[i] - 1)
		dp1[i][0] = 0
		dp1[i][1] = dp1[i - 1][0] 
		dp1[i][2] = dp1[i - 1][1]
	else:
		dp0[i][0] = dp0[i - 1][0] + 9
		dp0[i][1] = dp0[i - 1][1] + dp0[i - 1][0] * 9
		dp0[i][2] = dp0[i - 1][2] + dp0[i - 1][1] * 9
		dp1[i][0] = dp1[i - 1][0] 
		dp1[i][1] = dp1[i - 1][1] 
		dp1[i][2] = dp1[i - 1][2]


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

Submission status: Accepted

Solution code:
# 数字の文字列s
s = input()

# 非0桁の数
not_zero = int(input())

# 桁数
n = len(s)

# dp[決定済み桁数][未満フラグ][非0の桁数]
# 決定済み桁数: 0～n  今回の問題は 1<n<10の100乗 のため、nが最大100桁で多めに105桁を取る。
# 未満フラグ: 0:そこまでの桁がnと一致  1:そこまでの桁がnより小さい
# 非0の桁数: 0～k  1<=k<=3のため、多めに4を取る。
dp = [[[0] * 4 for i in range(2)] for j in range(105)]

# 初期化 空集合を作成
dp[0][0][0] = 1

for i in range(n):
    for j in range(2):
        for k in range(4):
            nd = int(s[i])
            for d in range(10):
                # 配る先
                ni = i + 1
                nj = j
                nk = k

                # 現在の桁が0でなければ、0の桁が一つ増えるため、配る先はnk += 1
                if d != 0:
                    nk += 1
                # 0の桁が指定より多い場合、配るのをやめる
                if nk > not_zero:
                    continue
                # 今までの桁と一致する場合
                if j == 0:
                    # 今までの桁が一致し、現在の桁がnの該当桁より大きい場合、配るのをやめる
                    if d > nd:
                        continue
                    # 今までの桁が一致し、現在の桁がnの該当桁より小さい場合、n未満に配る
                    if d < nd:
                        nj = 1
                dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

Solution code:
n_str = input()
k = int(input())

def k1(n_str):
	n_str = str(int(n_str))
	n_len = len(n_str)
	return 9*(n_len-1) + int(n_str[0])

def k2(n_str):
    s = 0
    n_str = str(int(n_str))
    n_len = len(n_str)
    if n_len < 2:
        return 0
    s += k2('9'*(n_len - 1))
    s += k1('9'*(n_len - 1)) * (int(n_str[0]) - 1)
    s += k1(n_str[1:])
    return s
                      
def k3(n_str):
    s = 0
    n_str = str(int(n_str))
    n_len = len(n_str)
    if n_len < 3:
        return 0
    s += k3('9'*(n_len - 1))
    s += k2('9'*(n_len - 1)) * (int(n_str[0]) - 1)
    s += k2(n_str[1:])
    return s

if k == 1:
    print(k1(n_str))
elif k == 2:
    print(k2(n_str))
elif k == 3:
    print(k3(n_str))

Submission status: Accepted

Solution code:
import math

N=input().replace('\n','')
K=int(input().replace('\n',''))

def C(n,k):
    return (math.factorial(n)//math.factorial(n-k))//math.factorial(k)

def calc(n,k):
    if n<k or k<0:
        return 0
    return (9**k)*C(n,k)

s=0
l=len(N)
counter=0
for i,num in enumerate(N):
    if (K-counter)==0:
        s+=1
        break
    if int(num)==0:
        continue
    if i==l-1:
        s+=(int(num))*calc(l-i-1,K-counter-1)
    else:
        s+=(int(num)-1)*calc(l-i-1,K-counter-1)
    s+=calc(l-i-1,K-counter)
    counter+=1

print(s)

Submission status: Accepted

Solution code:
n = int(input())
N = len(str(n))
k = int(input())
s = [int(i) for i in str(n)]
dpi = [[0]*(k+1) for _ in range(N+1)]
dpj = [[0]*(k+1) for _ in range(N+1)]
dpi[0][0] = 1
for i in range(N):
    for j in range(k+1):
        dpi[i+1][j] += dpi[i][j]*(s[i]==0)
        dpj[i+1][j] += dpj[i][j]+dpi[i][j]*(s[i]>0)
        if j < k:
            dpi[i+1][j+1]+=dpi[i][j]*(s[i]>0)
            dpj[i+1][j+1]+=dpj[i][j]*9+dpi[i][j]*max(0,s[i]-1)
print(dpi[N][k]+dpj[N][k])

Submission status: Accepted

Solution code:
from itertools import product

dp = [[[0 for k in range(2)] for j in range(5)] for i in range(105)]

s = input()
n = len(s)
K = int(input())

#i:桁
#j:ゼロ以外の数
#k:上限フラグ
dp[0][0][0] = 1

for i, j, k in product(range(n), range(0,4),(0,1)):
  nd=int(s[i])
#  print(i,j,k)
  for d in range(0,10):
    ni,nj,nk=i+1,j,k
    #ゼロ以外だったらjをカウントアップ
    if d!=0:
      nj+=1
    #jがKより大きくなったらスキップ
    if nj>K:
      continue
    #ここまでの桁が上限に達している場合
    if k==0:
    #上限の桁を超えた場合スキップ
      if d>nd:
        continue
    #この桁は上限未満
      elif d<nd:
        nk=1
#    print(i,j,k,ni,nj,nk)
    dp[ni][nj][nk]+=dp[i][j][k]
#    print(dp[ni][nj][nk])
print(dp[n][K][0]+dp[n][K][1])

Submission status: Accepted

Solution code:
n=input()
keta=len(n)
k=int(input())
#上からi桁、0以外の数がk個、smallerはless flag

dp=[[[0]*2 for _ in range(4)] for _ in range(keta +1 )]
dp[0][0][0]=1
for i in range(keta):
    for j in range(4):
        for smaller in range(2):
            nd = int(n[i]) #見ている桁の数字
            for d in range(10):
                #遷移先の数字をn付きで定義しておく
                ni=i+1
                nj=j
                nsmaller=smaller
                #変数ごとに条件を見ていく
                #iは必ず1ずつ増える
                #jについて
                if d!=0:
                    nj+=1
                if nj > k:
                    continue  #条件に合わないのはcontinueで飛ばす
                #smallerについて
                if smaller ==0:  # 今までnと同じで来ている
                    if d > nd:
                        continue
                    if d <nd:
                        nsmaller=1
                #最後はこれで足し合わせてfinish
                dp[ni][nj][nsmaller]+=dp[i][j][smaller]
ans = dp[keta][k][0]+dp[keta][k][1]
print(ans)

Submission status: Accepted

Solution code:
n = input()
k = int(input())
dp0 = [0] * 4
dp1 = [1,0,0,0]
for i in n:
  i = int(i)
  pdp0,pdp1,dp0 = dp0,dp1,[0]*4
  if i != 0:
    dp1 = [0] + pdp1[:-1]
  else:
    dp1 = pdp1
  dp0[0] = pdp0[0]+(i!=0)*pdp1[0]
  for j in range(1,4):
    dp0[j] = 9*pdp0[j-1] + pdp0[j] + (i!=0)*(i-1)*pdp1[j-1] + (i!=0)*pdp1[j]
print(dp0[k]+dp1[k])