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:
N_string = input()
l = len(N_string)
N = int(N_string)
K = int(input())

n = int(N_string[0])
dp0 = [[n - 1, 0, 0]]
dp1 = [[1, 0, 0]]

for i in range(l - 1):
    n = int(N_string[i + 1])
    if n == 0:
        dp0.append([9 + dp0[i][0],
                    dp0[i][0] * 9 + dp0[i][1],
                    dp0[i][1] * 9 + dp0[i][2]])
        dp1.append([dp1[i][0], dp1[i][1], dp1[i][2]])
    else:
        dp0.append([9 + dp0[i][0] + dp1[i][0],
                    dp0[i][0] * 9 + dp0[i][1] + dp1[i][0] * (n - 1) + dp1[i][1],
                    dp0[i][1] * 9 + dp0[i][2] + dp1[i][1] * (n - 1) + dp1[i][2]])
        dp1.append([0, dp1[i][0], dp1[i][1]])
print(dp0[-1][K - 1] + dp1[-1][K - 1])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, read().split())
    k = int(math.log(N, 10))
    s = N // (10 ** k)

    tmp1, tmp2, div = 1, 1, 1
    for i in range(K-1):
        tmp1 *= k-i
        div *= i+1
        tmp2 *= 9
    ret = tmp1//div * tmp2
    ret *= s-1

    tmp1 *= k - (K-1)
    tmp2 *= 9
    div *= K

    ret += tmp1 * tmp2 // div
    lis = range(k)
    nums = range(1,10)
    base = s * 10 ** k

    for A in combinations(lis, K-1):
        for X in product(nums, repeat = K-1):
            tmp = base
            for a,x in zip(A,X):
                tmp += 10 ** a * x
            if tmp <= N:
                ret += 1
    print(ret)



if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# 約分してから計算するアルゴリズム

def combination(n, r):
    # n >= 0, r >= 0, r <= n を仮定
    if n < 0 or r < 0 or n < r:
        return 0

    # r <= n - r を仮定
    if n - r < r:
        r = n - r

    # r < 2 の場合
    if r == 0:
        return 1
    if r == 1:
        return n

    # nCr の分子
    # [n - r + 1, n - r + 2, ... , n - 1, n]
    numerator = [n - r + 1 + i for i in range(r)]


    # nCr の分母
    # [1, 2, ... , r - 1, r]
    denominator = [i + 1 for i in range(r)]

    # nCr を約分する
    for i in range(r):
        # i番目の分母で約分する
        # 0番目は1なので省略

        # 元の（今までの約分を行う前の）i番目の分母の値
        original_denominator = i + 1

        # 今までの約分を行った後の、i番目の分母の値
        # 今回の約分で割る数
        divisor = denominator[i]

        # divisorが1（全て約分済み）の場合は無視する
        if divisor == 1:
            continue

        # 約分する相手の分子を決める
        # 0～i番目の分子（約分前）の中で、
        # original_denominatorで割り切れる数
        # （一つしかない）を選ぶ
        # remainder = i番目の分子 % original_denominator
        # とするとき、
        # (i - remainder)番目の分子 = i番目の分子 - remainder
        # (i - remainder)番目の分子 % original_denominator
        #  = (i番目の分子 - remainder) % original_denominator
        #  = 0
        # なので、(i - remainder)番目の分子を選べばよい。

        # remainder = i番目の分子 % original_denominator
        #           = (n - r + i + 1) % (i + 1)
        #           = (n - r) % (i + 1)
        remainder = (n - r) % original_denominator

        # divisor で約分できるペアをすべて約分する
        for j in range(i, r, original_denominator):
            numerator[j - remainder] = numerator[j - remainder] // divisor
            denominator[j] = denominator[j] // divisor

    ans = 1
    for i in numerator:
        ans *= i
    return ans


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

if N < 10:
    if K == 1:
        print(N)
    else:
        print(0)
# elif N < 100:
#     if K == 1:
#         print(9 + N // 10)
#     elif K == 2:
#         print(9 * (N // 10 - 1) + (N - (N // 10) * 10))
#     else:
#         print(0)
else:
    # 10 ** n <= N < 10 ** (n + 1) なる n
    # すなわち、N が n + 1 桁であるような n
    n = len(N_string) - 1

    # 10 ** n 未満で条件を満たす整数の数
    ans = combination(n, K) * (9 ** K)

    # Nの先頭の数字
    a = int(N_string[0])

    if K == 1:
        ans += a
    else:
        # a以外に0でない数字が出現するかどうか
        if N_string[1:] == "0" * n:
            # 出現しないとき
            ans += (a - 1) * combination(n, K - 1) * (9 ** (K - 1))
        else:
            # 出現するとき
            # Nの2番目の0以外の数字とその表れる桁数を計算
            m = n - 1
            while True:
                if N_string[n - m] != "0":
                    b = int(N_string[n - m])
                    break
                m -= 1

            if K == 2:
                # n + 1 桁かつ、先頭の数字が1以上a未満であるような、
                # 問題の条件を満たす整数の個数
                ans += (a - 1) * combination(n, K - 1) * 9

                # n + 1 桁かつ、先頭の数字が　a　であるような、
                # 問題の条件を満たす整数でN以下のもののの個数
                ans += combination(m, 1) * 9 + b
            else:
                # K == 3
                # a, b以外に0でない数字が出現するかどうか
                if N_string[n - m + 1:] == "0" * m:
                    # 出現しないとき

                    # n + 1 桁かつ、先頭の数字が1以上a未満であるような、
                    # 問題の条件を満たす整数の個数
                    ans += (a - 1) * combination(n, 2) * 9 * 9

                    # n + 1 桁で先頭の数字が　a　かつ、 m + 1 桁目が0であるような、
                    # 問題の条件を満たす整数でN以下のもののの個数
                    ans += combination(m, 2) * 9 * 9

                    # n + 1 桁で先頭の数字が a かつ、
                    # m + 1 桁目の数字が1以上b未満であるような、
                    # 問題の条件を満たす整数の個数
                    ans += (b - 1) * combination(m, 1) * 9
                else:
                    # Nの3番目の0以外の数字とその表れる桁数を計算
                    l = m - 1
                    while True:
                        if N_string[n - l] != "0":
                            c = int(N_string[n - l])
                            break
                        l -= 1

                    # n + 1 桁かつ、先頭の数字が1以上a未満であるような、
                    # 問題の条件を満たす整数の個数
                    ans += (a - 1) * combination(n, K - 1) * 9 * 9

                    # n + 1 桁で先頭の数字が　a　かつ、 m + 1 桁目が0であるような、
                    # 問題の条件を満たす整数でN以下のもののの個数
                    ans += combination(m, K - 1) * 9 * 9

                    # n + 1 桁で先頭の数字が a かつ、
                    # m + 1 桁目の数字が1以上b未満であるような、
                    # 問題の条件を満たす整数の個数
                    ans += (b - 1) * combination(m, K - 2) * 9

                    # n + 1 桁で先頭の数字が a かつ、
                    # m + 1 桁目の数字が　b　であるような、
                    # 問題の条件を満たす整数でN以下のもののの個数
                    ans += combination(l, 1) * 9 + c

    print(ans)

Submission status: Accepted

Solution code:
N = list(map(int,list(input())))
K = int(input())
L = len(N)
dp1 = [[0 for i in range(K+1)] for j in range(L+1)]
dp2 = [[0 for i in range(K+1)] for j in range(L+1)]
dp1[0][0] = 1

for i in range(L):
    for j in range(K+1):
        if N[i] == 0:
            dp1[i+1][j] += dp1[i][j]
        else:
            dp2[i+1][j] += dp1[i][j]
            if j > 0:
                dp1[i+1][j] += dp1[i][j-1]
                dp2[i+1][j] += dp1[i][j-1] * (N[i] - 1)
        if j > 0:
            dp2[i+1][j] += dp2[i][j-1] * 9
        dp2[i+1][j] += dp2[i][j]

ans = dp1[L][K] + dp2[L][K]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
n = str(N)
ln = len(n)
K = int(input())
dp0= [[0] * (K+2) for i in range(ln+1)]
#上からi桁目まで決めて、0でない桁がj個あり、Nより小さいことが確定している
dp1 = [[0] * (K+2) for i in range(ln+1)]
#上からi桁目まで決めて、0でない桁がj個あり、Nより小さいことが確定していない

dp1[0][0] = 1

for i in range(ln):
  x = int(n[i])
  dp0[i+1][0] = 1
  for j in range(K):
    if(x == 0):
      dp0[i+1][j+1] = 9*dp0[i][j]+dp0[i][j+1]
      dp1[i+1][j+1] = dp1[i][j+1]
    else:
      dp0[i+1][j+1] = 9*dp0[i][j]+dp0[i][j+1]+(x-1)*dp1[i][j]+dp1[i][j+1]
      dp1[i+1][j+1] = dp1[i][j]
  #print(dp0)
  #print(dp1)
print(dp0[ln][K]+dp1[ln][K])

Submission status: Accepted

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

digit = len(str(n))
# dp[i桁まで検査済み][coincidence][0以外の個数]
dp = [[[0] * (k + 1) for i in range(2)] for j in range(digit + 1)]

dp[0][1][0] = 1
for a in range(1, digit + 1):
    digitvalue = int(str(n)[a - 1])
    for c in range(k + 1):
        if c == k:
            # 最大値と不一致で0以外の個数がk個になる
            dp[a][0][c] += dp[a-1][0][k] * 1
            dp[a][0][c] += dp[a-1][0][k-1] * 9
            # d != 0(仮に3) -> 0
            # d == 0 -> 0にすると最大値と一致するのでだめ
            dp[a][0][c] += dp[a-1][1][k] * (1 if digitvalue != 0 else 0)
            # d != 0(仮に3) -> 1, 2(0はkにならないのでだめ、3はb == 1になるのでだめ)
            # d == 0 -> 0にするとkが増えないのでだめ
            dp[a][0][c] += dp[a-1][1][k-1] * (digitvalue - 1 if digitvalue != 0 else 0)
            # 最大値と一致で0以外の個数がk個になる
            dp[a][1][c] += dp[a-1][1][k] * (1 if digitvalue == 0 else 0)
            dp[a][1][c] += dp[a-1][1][k-1] * (1 if digitvalue != 0 else 0)
        elif c != k:
            # 最大値と不一致で0以外の個数がc個になる
            dp[a][0][c] += dp[a-1][0][c] * 1
            dp[a][0][c] += 0 if c == 0 else dp[a-1][0][c-1] * 9
            dp[a][0][c] += dp[a-1][1][c] * (1 if digitvalue != 0 else 0)
            dp[a][0][c] += 0 if c == 0 else dp[a-1][1][c-1] * (digitvalue - 1 if digitvalue != 0 else 0)
            dp[a][1][c] += dp[a - 1][1][c] * (1 if digitvalue == 0 else 0)
            dp[a][1][c] += 0 if c == 0 else dp[a - 1][1][c - 1] * (1 if digitvalue != 0 else 0)
        else:
            None
#     print("--", a)
#     for i in range(k + 1):
#         print(dp[a][0][i])
#     for i in range(k + 1):
#         print(dp[a][1][i])

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

Submission status: Accepted

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

keta = len(str(n))
# dp[i桁まで検査済み][coincidence][0以外の個数]
dp = [[[0] * (k + 1) for i in range(2)] for j in range(keta + 1)]

dp[0][1][0] = 1
for a in range(1, keta + 1):
    digit = int(str(n)[a - 1])
    for b in range(2):
        for c in range(k + 1):
            if b == 0 and c == k:
                # 最大値と不一致で0以外の個数がk個になる
                dp[a][b][c] += dp[a-1][0][k] * 1
                dp[a][b][c] += dp[a-1][0][k-1] * 9
                # d != 0(仮に3) -> 0
                # d == 0 -> 0にすると最大値と一致するのでだめ
                dp[a][b][c] += dp[a-1][1][k] * (1 if digit != 0 else 0)
                # d != 0(仮に3) -> 1, 2(0はkにならないのでだめ、3はb == 1になるのでだめ)
                # d == 0 -> 0にするとkが増えないのでだめ
                dp[a][b][c] += dp[a-1][1][k-1] * (digit - 1 if digit != 0 else 0)
            elif b == 0 and c != k:
                # 最大値と不一致で0以外の個数がc個になる
                dp[a][b][c] += dp[a-1][0][c] * 1
                dp[a][b][c] += 0 if c == 0 else dp[a-1][0][c-1] * 9
                dp[a][b][c] += dp[a-1][1][c] * (1 if digit != 0 else 0)
                dp[a][b][c] += 0 if c == 0 else dp[a-1][1][c-1] * (digit - 1 if digit != 0 else 0)
            elif b == 1 and c == k:
                # 最大値と一致で0以外の個数がk個になる
                dp[a][b][c] += dp[a-1][1][k] * (1 if digit == 0 else 0)
                dp[a][b][c] += dp[a-1][1][k-1] * (1 if digit != 0 else 0)
            elif b == 1 and c != k:
                dp[a][b][c] += dp[a-1][1][c] * (1 if digit == 0 else 0)
                dp[a][b][c] += 0 if c == 0 else dp[a-1][1][c-1] * (1 if digit != 0 else 0)
            else:
                None
#     print("--", a)
#     for i in range(k + 1):
#         print(dp[a][0][i])
#     for i in range(k + 1):
#         print(dp[a][1][i])

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

Submission status: Accepted

Solution code:
def case_k1(n):
    digit = len(str(n))
    if digit ==1:
        return n
    else:
        return (n//(10**(digit-1))+(digit-1)*9)

def case_k2(n):
    digit = len(str(n))
    if digit == 1:
        return 0
    elif digit ==2:
        return (n//10-1)*9+n%10
    else:
        sum = 0
        for i in range(1,digit-1):
            sum += i*81
        q = n//(10**(digit-1))
        r = n-q*10**(digit-1)
        r_digit = len(str(r))
        sum += (q-1)*(case_k1(10**(digit-1)-1)) + case_k1(r)
        return sum

def case_k3(n):
    digit = len(str(n))
    if digit <3:
        return 0
    else:
        sum = 0
        for i in range(2,digit-1):
            sum += 9*case_k2(10**(i)-1)
        q = n//(10**(digit-1))
        r = n-q*10**(digit-1)
        sum += (q-1)*(case_k2(10**(digit-1)-1)) + case_k2(r)
        return sum

N = input()
K = int(input())
n = int(N)
if K ==1:
    print(case_k1(n))
elif K ==2:
    print(case_k2(n))
else:
    print(case_k3(n))

Submission status: Accepted

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

for i in range(1, len_n + 1):
    l = int(str(n)[i - 1])
    for m in range(k + 1):
        dp[i][1][m] += dp[i - 1][1][m]
        if l != 0:
            dp[i][1][m] += dp[i - 1][0][m]
        else:
            dp[i][0][m] += dp[i - 1][0][m]
        if m - 1 >= 0:
            dp[i][1][m] += 9 * dp[i - 1][1][m - 1]
            if l != 0:
                dp[i][0][m] += dp[i - 1][0][m - 1]
                dp[i][1][m] += (l - 1) * dp[i - 1][0][m - 1]

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

Submission status: Accepted

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

@lru_cache()
def f(n, k):
    if k == 0:
        return 1
    if len(n) == 1:
        if k == 1:
            return int(n)
        else:
            return 0
    m = int(n[-1])
    return f(n[:-1], k) + f(n[:-1], k - 1) * m + f(str(int(n[:-1]) - 1), k - 1) * (9 - m)

print(f(N, K))

Submission status: Accepted

Solution code:
def nCk(n,k):
    res = 1
    for i in range(k,0,-1):
        res = res*(n+1-i)/i
    return int(res)

N = input()
K = int(input())
ans = 0
dp_mikakutei = [[0 for i in range(0,K+1,1)] for j in range(0,len(N),1)]#Nより小さいかまだわからん
dp_kakutei = [[0 for i in range(0,K+1,1)] for j in range(0,len(N),1)]

dp_mikakutei[0][1]=1#その桁がまさにNのその桁と同じ
dp_kakutei[0][0]=1
dp_kakutei[0][1]=int(N[0])-1#1~N[0]-1

for i in range(1,len(N),1):
    dp_kakutei[i][0]=dp_kakutei[i-1][0] + dp_mikakutei[i-1][0]
    for j in range(1,K+1,1):
        if N[i] =="0":
            dp_mikakutei[i][j] = dp_mikakutei[i-1][j]
            dp_kakutei[i][j] = 9*dp_kakutei[i-1][j-1] +dp_kakutei[i-1][j]
        else:
            dp_mikakutei[i][j] = dp_mikakutei[i-1][j-1]
            dp_kakutei[i][j] = 9*dp_kakutei[i-1][j-1] + (int(N[i])-1)*dp_mikakutei[i-1][j-1] + dp_kakutei[i-1][j] + dp_mikakutei[i-1][j]
print(dp_mikakutei[len(N)-1][K] + dp_kakutei[len(N)-1][K])

Submission status: Accepted

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

# K = 1の時の組み合わせを求める関数
def func_1(N):
    Nm = int(N[0])
    return Nm + 9 * (len(N) - 1)

# K = 2の時の組み合わせを求める関数
def func_2(N):
    #NはStringなので
    #print(N[0])

    Nm = int(N[0])
    m = len(N)
    #if m == 1:
     #   print("0")
    #print((Nm-1)*(m-1)*9)
    #print((m - 1) * (m - 2) * 9 * 9 / 2)
    x = int(N) - Nm * pow(10, m-1)
    #print(x)
    #print(1)
    #print(func_1(str(x)))


    return  int((Nm-1)*(m-1)*9+(m-1)*(m-2)*9*9/2+func_1(str(x)))

def func_3(N):
    #print("OK")
    Nm = int(N[0])
    m = len(N)
   # if m == 1 or m == 2:
     #   print("0")
    return int(pow(9,3)*(m-1)*(m-2)*(m-3)/6+(Nm-1)*(m-1)*(m-2)*9*9/2+func_2(str(int(N)-Nm*(10**(m-1)))))



if K == 1:
    print(func_1(N))
elif K == 2:
    print(func_2(N))
elif K == 3:
    print(func_3(N))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N=input()
    K,=pin()

    #degit DP
    #dp_table["index"][smaller][cond]=cond:=ちょうどK個の数がある を満たす総数
    
    rb=(0,1)
    dp_table=[[[0 for cnd in range(K+1)]for sml in rb]for ind in range(len(N)+1)]
    dp_table[0][0][0]=1
    #print(dp_table)
    #print("degit,sml,k,prove,l,x<n,dp_table[degit-1][sml][k]")#
    for degit in range(len(N)+1):
        n=int(N[degit-1])
        for sml in rb:
            t=10 if sml else int(N[degit-1])+1
            for k in range(K+1):
                for prove in range(t):
                    x=prove
                    try:#Indexerror
                        #print(degit,sml,k,prove,"l",x<n,dp_table[degit-1][sml][k])
                        #if  sml==False  and x==n:print(n,":") 
                        dp_table[degit][sml or x<n][k+(x!=0)]+=dp_table[degit-1][sml][k]
                    except :pass

    print(dp_table[-1][0][K]+dp_table[-1][1][K])
    #print(dp_table)
#%%submit!
resolve()

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(1000000)


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

from functools import lru_cache

@lru_cache(maxsize=10000)
def f(n,k):
    # print('n:{},k:{}'.format(n,k))
    if k == 0:
        return 1
    if k== 1 and n < 10:
        return n

    keta = len(str(n))
    if keta < k:
        return 0

    h = n // (10 ** (keta-1))
    b = n % (10 ** (keta-1))

    ret = 0
    for i in range(h+1):
        if i==0:
            ret += f(10 ** (keta-1) - 1, k)
        elif 1 <= i < h:
            ret += f(10 ** (keta-1) - 1, k-1)
        else:
            ret += f(b,k-1)
        
    return ret

print(f(N,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:
s=input()
n=len(s)
K=int(input())
dp=[[[0,0] for _ in range(K+1)] for _ in range(n+1)]
dp[0][0][0]=1
r=range
for i in r(n):
  nd=int(s[i])
  for j in r(K+1):
    for k in r(2):
      for d in r(10):
        ni,nj,nk=i+1,j,k
        if d: nj+=1
        if nj>K: continue
        if k<1:
          if d>nd: continue
          if d<nd: nk=1
        dp[ni][nj][nk]+=dp[i][j][k]
print(dp[n][K][0]+dp[n][K][1])

Submission status: Accepted

Solution code:
def f(n,k):
  if k<1: return 1
  if n<10:
    if k<2: return n
    return 0
  d,m=n//10,n%10
  return f(d,k-1)*m+f(d-1,k-1)*(9-m)+f(d,k)
print(f(int(input()),int(input())))

Submission status: Accepted

Solution code:
from functools import lru_cache
@lru_cache(None)
def f(n,k):
  if k<1: return 1
  if n<10:
    if k<2: return n
    return 0
  d,m=n//10,n%10
  return f(d,k-1)*m+f(d-1,k-1)*(9-m)+f(d,k)
print(f(int(input()),int(input())))

Submission status: Accepted

Solution code:
from functools import lru_cache
@lru_cache(None)
def f(n,k):
  if n<10:
    if k<1: return 1
    if k<2: return n
    return 0
  d,m=divmod(n,10)
  c=0
  if k:
    c+=f(d,k-1)*m
    c+=f(d-1,k-1)*(9-m)
  c+=f(d,k)
  return c
print(f(int(input()),int(input())))

Submission status: Accepted

Solution code:
n="0"+input()
k=int(input())
dp=[[[0]*(k+1) for i in range(len(n))] for _ in range(2)]
dp[0][0][0]=1
dp[1][1][0]=1
for i in range(1,len(n)):
    x=int(n[i])
    dp[1][i][0]+=dp[1][i-1][0]
    for j in range(1,k+1):
        if x==0:
            dp[0][i][j]+=dp[0][i-1][j]
            dp[1][i][j]+=dp[1][i-1][j]+dp[1][i-1][j-1]*9
        else:
            dp[0][i][j]+=dp[0][i-1][j-1]
            dp[1][i][j]+=dp[1][i-1][j]+dp[1][i-1][j-1]*9+dp[0][i-1][j-1]*(x-1)+dp[0][i-1][j]
print(dp[1][-1][-1]+dp[0][-1][-1])

Submission status: Accepted

Solution code:
import math

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

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

for i in range(l):
    for j in range(4):
        for k in range(2):
            for d in range(10):
                nd = int(str(N)[i])
                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]

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

Submission status: Accepted

Solution code:
N=int(input())
K=int(input())
s=str(N)
N=len(s)

# dp[i][smaller][k] :=i桁目までで0以外の数を使用したのがk個である数の個数。
# smallerが1ならNより小さく、0ならNと等しい数であるとする。
dp=[[[0]*(K+2) for j in range(2)] for i in range(N+1)]
dp[0][0][0]=1
for i in range(N):
  for k in range(K+1):
    ni=int(s[i])
    # i桁目まででNより小さいならi+1桁目は何でも良い
    dp[i+1][1][k+1]+=dp[i][1][k]*9 # i+1桁目が0以外
    dp[i+1][1][k]+=dp[i][1][k]     # i+1桁目が0
    # i桁目まででNと同じで、i+1桁目はNより小さい時
    if ni>0:
      dp[i+1][1][k+1]+=dp[i][0][k]*(ni-1) # i+1桁目が0以外
      dp[i+1][1][k]+=dp[i][0][k]          # i+1桁目が0以外
    # i桁目までNと同じで、i+1桁目もNと同じ数の時
    if ni>0:
      dp[i+1][0][k+1]=dp[i][0][k] # i+1桁目が0以外
    else:
      dp[i+1][0][k]=dp[i][0][k]   # i+1桁目が0
print(dp[N][0][K]+dp[N][1][K])

Submission status: Accepted

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

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

for i in range(n):
  for k in range(K+1):
    x = int(s[i])
    
    dp[i+1][1][k+1] += dp[i][1][k] * 9
    dp[i+1][1][k]   += dp[i][1][k]        
    
    if x > 0:
      dp[i+1][1][k+1] += dp[i][0][k] * (x-1)
      dp[i+1][1][k]   += dp[i][0][k]
      dp[i+1][0][k+1] = dp[i][0][k]
    else:
      dp[i+1][0][k] = dp[i][0][k]
      
print( dp[n][0][k]+ dp[n][1][k])

Submission status: Accepted

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

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

Submission status: Accepted

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

OK=[[0 for k in range(5)]for i in range(len(N))]
OK[0][0]=1
OK[0][1]=int(N[0])-1
D=1
#print(OK)
for i in range(1,len(N)):
    OK[i][0]=OK[i-1][0]
    OK[i][1]+=OK[i-1][0]*9+OK[i-1][1]
    OK[i][2]+=OK[i-1][1]*9+OK[i-1][2]
    OK[i][3]+=OK[i-1][2]*9+OK[i-1][3]
    if D<=K and int(N[i])!=0:
        OK[i][D]+=1
        OK[i][D+1]+=int(N[i])-1
        D+=1
if D==K:
    print(OK[-1][K]+1)
else:
    print(OK[-1][K])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
ans = 0
for i in range(1,len(n)):
    if (i < k):
        continue
    else:
        if (k==1):
            ans += 9
        elif (k==2):
            ans += 9*(i-1)*9
        else:
            ans += 9*9*9*(i-1)*(i-2)//2
    #print(ans)
if (k==1):
    ans += int(n[0])
elif (k==2):
    ans += (int(n[0])-1)*(len(n)-1)*9
    #print(ans)
    for i in range(1,len(n)):
        if (int(n[i])>0):
            ans += 9*(len(n)-i-1)
            ans += int(n[i])
            break
        if (i==len(n)-1):
            print(ans)
            exit()
else:
    ans += (int(n[0])-1)*9*9*(len(n)-1)*(len(n)-2)//2
    for i in range(1,len(n)):
        if (int(n[i])>0):
            ans += (int(n[i])-1)*9*(len(n)-i-1)
            ans += 9*9*(len(n)-i-1)*(len(n)-i-2)//2
            t = i
            break
        if (i==len(n)-2):
            print(ans)
            exit()
    for j in range(t+1,len(n)):
        if (int(n[j])>0):
            ans += int(n[j])
            ans += 9*(len(n)-j-1)
            break
print(ans)

Submission status: Accepted

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

dp = [[[0 for _ in range(5)] for _ in range(2)] for _ in range(N+5)]
dp[1][0][1] = 1
dp[1][1][0] = 1
dp[1][1][1] = int(S[0])-1

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

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

Submission status: Accepted

Solution code:
#WA

#桁DP

N=str(input())
K=int(input())
L=len(N)

#DP[i][smaller][j]=上からi桁(1<=i<=L)で0でない数字がj個(0<=j<=3)
DP=[[[0]*5 for index1 in range(2)] for index2 in range(L+1)]
#適当に初期設定
DP[0][0][0]=1



for i in range(1,L+1):
    #smaller=1->smaller=1
    DP[i][1][4]+=DP[i-1][1][4]*10+DP[i-1][1][3]*9
    DP[i][1][3]+=DP[i-1][1][3]+DP[i-1][1][2]*9
    DP[i][1][2]+=DP[i-1][1][2]+DP[i-1][1][1]*9
    DP[i][1][1]+=DP[i-1][1][1]+DP[i-1][1][0]*9
    DP[i][1][0]+=DP[i-1][1][0]

    n=int(N[i-1])

    #smaller=0->smaller=1
    #n=0だとsmaller=0->smaller=1がない
    #n=1だとsmaller=0->smaller=1のとき必ずjは変化しない
    if n==1:
        DP[i][1][4]+=DP[i-1][0][4]
        DP[i][1][3]+=DP[i-1][0][3]
        DP[i][1][2]+=DP[i-1][0][2]
        DP[i][1][1]+=DP[i-1][0][1]
        DP[i][1][0]+=DP[i-1][0][0]
    elif n>=2:
        DP[i][1][4]+=DP[i-1][0][4]*n+DP[i-1][0][3]*(n-1)
        DP[i][1][3]+=DP[i-1][0][3]+DP[i-1][0][2]*(n-1)
        DP[i][1][2]+=DP[i-1][0][2]+DP[i-1][0][1]*(n-1)
        DP[i][1][1]+=DP[i-1][0][1]+DP[i-1][0][0]*(n-1)
        DP[i][1][0]+=DP[i-1][0][0]

    #smaller=0->smaller=0
    #n=0だと必ずjは変化しない
    if n==0:
        DP[i][0][4]+=DP[i-1][0][4]
        DP[i][0][3]+=DP[i-1][0][3]
        DP[i][0][2]+=DP[i-1][0][2]
        DP[i][0][1]+=DP[i-1][0][1]
        DP[i][0][0]+=DP[i-1][0][0]
    else:
        DP[i][0][4]+=DP[i-1][0][4]+DP[i-1][0][3]
        DP[i][0][3]+=DP[i-1][0][2]
        DP[i][0][2]+=DP[i-1][0][1]
        DP[i][0][1]+=DP[i-1][0][0]

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = input().rstrip()
    k = int(input())
    ln = len(n)
    # dp[i][j]:左からi桁まで見たとき0でない桁がj個ある場合の数
    dp1 = [[0]*(k+1) for _ in range(ln+1)]
    dp2 = [[0]*(k+1) for _ in range(ln+1)]

    dp2[0][0] = 1
    cnt = 0
    for i in range(ln):
        if n[i] != '0':
            if cnt < k:
                cnt += 1
            dp2[i+1][cnt] = 1
        else:
            dp2[i+1][cnt] = dp2[i][cnt]

    for i in range(ln):
        dp1[i+1][0] = 1
        for j in range(1, k+1):
            dp1[i+1][j] += dp1[i][j] + dp1[i][j-1] * 9
            if n[i] != '0':
                dp1[i+1][j] += dp2[i][j-1] * (int(n[i])-1)
                if j < k:
                    dp1[i+1][j] += dp2[i][j]
    print(dp1[-1][k] + dp2[-1][k])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# dp[digit][smaller][used # of non-0]
# dp[i][j][l]
dp = [[[0 for _ in range(k+2)] for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0]=1

for i in range(len(n)):
    nd = int(n[i])
    for j in [0, 1]:
        for l in range(k+1):
            for d in range(10):
                ni=i+1
                nj=j
                nl=l

                if d!=0:
                    nl+=1
                if nl>k:
                    continue
                if j==0: # equal to n
                    if d > nd:
                        continue
                    if d < nd:
                        nj=1 # smaller
                dp[ni][nj][nl] += dp[i][j][l]

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7
    def ncr(n, r, mod):
        r = min(r, n-r)
        numer = denom = 1
        for i in range(1, r+1):
            numer = numer * (n+1-i) % mod
            denom = denom * i % mod
        return numer * pow(denom, mod-2, mod) % mod

    n = input().rstrip()
    k = int(input())
    ln = len(n)
    if ln < k:
        print(0)
        exit()
    res = 0
    if k == 1:
        if ln >= 2:
            res += ncr(ln-1, 1, mod) * 9
        res += int(n[0])
    if k == 2:
        if ln >= 3:
            res += ncr(ln-1, 2, mod) * (9**k)
        res += ncr(ln-1, 1, mod) * 9 * (int(n[0])-1)
        for i in range(1, ln):
            if n[i] != '0':
                if i == ln-1:
                    res += int(n[i])
                else:
                    res += ncr(ln-i-1, 1, mod) * 9
                    res += int(n[i])
                break
    if k == 3:
        if ln >= 4:
            res += ncr(ln-1, 3, mod) * (9**k)
        res += ncr(ln-1, 2, mod) * 81 * (int(n[0])-1)
        for i in range(1, ln-1):
            if n[i] != '0':
                if ln-i-1 >= 2:
                    res += ncr(ln-i-1, 2, mod) * 81
                res += ncr(ln-i-1, 1, mod) * 9 * (int(n[i])-1)
                for j in range(i+1, ln):
                    if n[j] != '0':
                        if j != ln-1:
                            res += ncr(ln-j-1, 1, mod) * 9 
                        res += int(n[j])
                        break
                break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=input()
cnt=int(input())
L=len(N)
dp=[[[0]*(cnt+1) for j in range(2)] for i in range(L+1)]
dp[0][0][0]=1
for i in range(L):
    for j in range(2):
        for k in range(cnt+1):
            D=int(N[i])
            for d in range(10 if j else D+1):
                K=k+int(d!=0)
                if K>cnt:
                    continue
                dp[i+1][int(j or d<D)][K]+=dp[i][j][k]
print(dp[-1][0][-1]+dp[-1][1][-1])

Submission status: Accepted

Solution code:
S = list(map(int,list(input())))
K = int(input())
from itertools import groupby, accumulate, product, permutations, combinations
def solve(S,K):
    ans = 0
    n = len(S)
    dp1 = [[0]*5 for _ in range(n)]
    dp0 = [[0]*5 for _ in range(n)]
    dp0[0][1] = 1
    dp1[0][0] = 1
    dp1[0][1] = S[0]-1
    for i in range(1,n):
        for j in range(4):
            dp1[i][j] = dp1[i-1][j]+dp1[i-1][j-1]*9
            if S[i]==0:
                dp0[i][j] = dp0[i-1][j]
            else:
                dp0[i][j] = dp0[i-1][j-1]
                dp1[i][j] += dp0[i-1][j-1]*(S[i]-1)+dp0[i-1][j]
    ans = dp1[n-1][K]+dp0[n-1][K]
    return ans
print(solve(S,K))