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:
import numpy as np

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

print(ans)

Submission status: Accepted

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

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

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

print(func(N,K))

Submission status: Accepted

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

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

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

print(func(N,K))

Submission status: Accepted

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


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

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

print(func(N,K))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# from scipy.special import comb
sys.setrecursionlimit(10**4)
from math import factorial

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

def f(S, i, k):
    # ここに来るのは繰り下がりが発生していない状態...
    if k == 0:
        # 以降は0を選び続けるしかない
        return 1
    if len(S) <= i:
        # 走破したのにK個使いきれていない
        return 0
    n = int(S[i])
    if n == 0:
        # 注目する桁が0の場合、0を選ぶしかない
        return f(S, i+1, k)
    # 注目する桁の数値nより小さい値を選べば、以降は繰り下げで選び放題
    ret = (n - 1) * comb(len(S)-i-1, k-1) * pow(9, k-1)
    ret += comb(len(S)-i-1, k) * pow(9, k)
    # 注目する桁の数値nを選んだ場合、繰り下げができない状態が続行    
    ret += f(S, i+1, k-1)
    return ret

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


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    print(solve(N, K))

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

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

Submission status: Accepted

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

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


def solve():

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

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

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

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

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

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

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

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#  愚直に数え上げる方法

import sys

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


def solve():

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

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

    elif K == 2:

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

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

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

    elif K == 3:

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

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

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


def solve():

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

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

    elif K == 2:

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

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

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

    elif K == 3:

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

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

K=int(input())

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

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

    for k in range(4):
            # smaller 1 -> 全部OK
            dp[i + 1][1][k + 1] += dp[i][1][k] * 9;  
            dp[i + 1][1][k] += dp[i][1][k];  

            # smaller 0,next smaller 1 -> nowより小さいのを全部
            # 次の桁からsmallerであるためにはN＜ni であることが必要で
            # Nは0より大きい必要がある。（0より小さいものがない＝確定しない
            if (ni > 0):
                dp[i + 1][1][k + 1] += dp[i][0][k] * (ni - 1)
                dp[i + 1][1][k] += dp[i][0][k]
                
            # smaller 0,next smaller 0 -> nowだけ
            if (ni > 0) :
                dp[i + 1][0][k + 1] = dp[i][0][k]
            else:
                dp[i + 1][0][k] = dp[i][0][k]

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

Submission status: Accepted

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

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

for i in range(1, len(n) + 1):
    t = int(n[i-1])
    for j in range(k+1):
        if t != 0:
            if j != 0:
                dp[i][0][j] += dp[i-1][0][j-1]
                dp[i][1][j] += dp[i-1][1][j-1] * 9 + dp[i-1][0][j-1] * (t-1)
            dp[i][1][j] += (dp[i-1][1][j] + dp[i-1][0][j])
        else:
            dp[i][0][j] += dp[i-1][0][j]
            if j != 0:
                dp[i][1][j] += dp[i-1][1][j-1] * 9
            dp[i][1][j] += dp[i-1][1][j]

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

Submission status: Accepted

Solution code:
n = int(input())
k = int(input())
ns = str(n)
digits = len(ns)
dp = [[[0, 0, 0, 0] for i in range(2)] for i in range(digits + 1)]
#dp[i + 1][flag][j]:= 上からi桁目までで条件を満たす数
#flag = 0: 取り出したi桁目までが一致している(次の桁の制約ができる)
#j: 0~3　出てきた0以外の数字の数

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

            if t == 0:
                #上位の桁による制約を受ける

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

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

            else:
                #上位の桁からの制約がない
                for i in range(10):
                    if i == 0:
                        dp[s + 1][t][u] += temp
                    elif i != 0 and u + 1 < 4:
                        dp[s + 1][t][u + 1] += temp

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

dp[0][0][0]=1
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])

            for d in range(10):
                ni = i+1; nj = j; nk = k

                if d != 0 :nj+=1
                if nj > K:continue
                if k==0:
                    if d > nd:continue
                    if d < nd:nk =1
                dp[ni][nj][nk] += dp[i][j][k]
                # print(d,k)
                # print(i,j,k,dp[i][j][k])
                # print(ni,nj,nk,dp[ni][nj][nk])
                # [print(i) for i in dp]

ans=dp[n][K][0] + dp[n][K][1]
print(ans)
# [print(i) for i in dp]

Submission status: Accepted

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

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

dp[0][0][0]=1
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])- 0

            for d in range(10):
                ni = i+1; nj = j; nk = k

                if d != 0 :nj+=1
                if nj > K:continue
                if k==0:
                    if d > nd:continue
                    if d < nd:nk =1

                dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

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

@lru_cache(None)
def f(N, K):
    #大きい桁から小さい桁へ
    if K < 0:
        return 0
    if N < 10:
        if K == 0:
            # 0のみ
            return 1
        elif K == 1:
            # 例えばN=4 なら0でないものが1,2,3,4の合計4個存在
            return N
        else:
            return 0
    q, r = divmod(N, 10)
    ret = 0
    if K >= 1:
        # 1の位が0以外の場合Kを消費する
        ret += f(q, K-1) * r
        ret += f(q-1, K-1) * (9-r)
    # 1の位が0の場合
    ret += f(q, K)
    return ret

print(f(N, K))

Submission status: Accepted

Solution code:
import math

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

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

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

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

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

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

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


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

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

Submission status: Accepted

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

n = len(N)

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

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

Submission status: Accepted

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

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

#10
#0の数は高々3つまでなので、jは0,1,2,3の配列だけ持てば良い
#i桁目までは高々100
#
#dp[i][j][smaller]=

lenn=len(str(n))

dp=[[[0]*2 for _ in range(4)]  for _ in range(lenn)]
#smallerは、0：:通常、1:未満の2パターン

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

#print(dp)

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

stdin = sys.stdin

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

n = ns()
k = ni()
dp = [[[0]*2 for _ in range(k+1)] for _ in range(len(n)+1)]
dp[0][0][0] = 1
for i in range(len(n)):
    x = int(n[i])
    for j in range(k):
        dp[i+1][j+1][1] += dp[i][j][1]*9
        dp[i+1][j][1] += dp[i][j][1]
        if x > 0:
            dp[i+1][j][1] += dp[i][j][0]
            dp[i+1][j+1][1] += dp[i][j][0]*(x-1)
            dp[i+1][j+1][0] += dp[i][j][0]
        else:
            dp[i+1][j][0] += dp[i][j][0]
    dp[i+1][k][1] += dp[i][k][1]
    dp[i+1][k][x>0] += dp[i][k][0]
    #インデックスjのところが拾いきれていないので拾う
    #iとkはぶつかっていないので普通に二重ループでかける
print(sum(dp[len(n)][k]))

Submission status: Accepted

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

l=len(N)

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

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

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

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

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

Submission status: Accepted

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

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

    # dp[i][j][k]
    # i 桁目まで決めて
    # j 個の非0を使って
    # k = 0 : そこまでの桁はNと一致
    # k = 1 : そこまでの桁でN未満であることが確定
    dp = [[[0] * 2 for _ in range(K + 2)] for _ in range(L + 1)]
    dp[0][0][0] = 1

    for i, x in enumerate(N):
        for k in range(K + 1):
            # 桁ごと数え上げ
            if x == 0:
                # x == 0
                dp[i + 1][k][0] += dp[i][k][0]
            else:
                # x == 0
                dp[i + 1][k][1] += dp[i][k][0]
                # 0 < n < x
                dp[i + 1][k + 1][1] += dp[i][k][0] * (x - 1)
                # n == x
                dp[i + 1][k + 1][0] += dp[i][k][0]
            # N未満で次の桁に1~9を入れる
            dp[i + 1][k + 1][1] += dp[i][k][1] * 9
            # N未満で次の桁に0を入れる
            dp[i + 1][k][1] += dp[i][k][1]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    # dp[i][j][k]
    # i 桁目まで決めて
    # j 個の非0を使って
    # k = 0 : そこまでの桁はNと一致
    # k = 1 : そこまでの桁でN未満であることが確定
    dp = [[[0] * 2 for _ in range(K + 2)] for _ in range(L + 1)]
    dp[0][0][0] = 1

    from pprint import pprint
    for i, x in enumerate(N):
        for k in range(K + 1):
            # 桁ごと数え上げ
            if x == 0:
                # x == 0
                dp[i + 1][k][0] += dp[i][k][0]
            else:
                # x == 0
                dp[i + 1][k][1] += dp[i][k][0]
                # 0 < n < x
                dp[i + 1][k + 1][1] += dp[i][k][0] * (x - 1)
                # n == x
                dp[i + 1][k + 1][0] += dp[i][k][0]
            # N未満で次の桁に1~9を入れる
            dp[i + 1][k + 1][1] += dp[i][k][1] * 9
            # N未満で次の桁に0を入れる
            dp[i + 1][k][1] += dp[i][k][1]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import itertools

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

f = len(str(n))

if f < k:
    print(0)
else:
    #f-1桁以内に収まる数

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

    de = math.factorial(k)


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


    #f桁目によって絞る

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

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

    de = math.factorial(k-1)


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


    #以下上1桁は同じ数字

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

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


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

    print(s)

Submission status: Accepted

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

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

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

    for i, x in enumerate(S):
        for k in range(K + 1):  # ここをrange(K)にしてバグらせた
            if x == 0:
                dp[i + 1][k][EQ] += dp[i][k][EQ]  # x
            else:
                dp[i + 1][k + 1][EQ] += dp[i][k][EQ]  # x
                dp[i + 1][k + 1][LESS] += dp[i][k][EQ] * (x - 1)  # <x
                dp[i + 1][k][LESS] += dp[i][k][EQ]  # ==0
            dp[i + 1][k + 1][LESS] += dp[i][k][LESS] * 9  # !=0
            dp[i + 1][k][LESS] += dp[i][k][LESS]  # ==0

    print(sum(dp[L][K]))  # 全部0はK個の0でない数字を含まないので除去する必要がない


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(n_len):
    for j in range(k+1):
        # iでTrue、i+1でTrueのとき（i桁目が０でないとき、ｋは減る）
        # かける９の意味は０以外のなんでもいい数ということ
        dp[i+1][True][j+1] += dp[i][True][j]*9
        # iでTrue、i+1でTrueのとき（i桁目が０のとき、ｋは減らない）
        # ０一択なので＊１
        dp[i+1][True][j] += dp[i][True][j]*1

        # i桁目まで等しい状態からi+1桁目で小さくなるとき
        # i⁺1桁目が０だったら小さくなりようがないので考えない
        # i+1桁目が０のときはもう一つ下の場合分けに入っている
        if int(n[i]) != 0:
            dp[i+1][True][j+1] += dp[i][False][j]*(int(n[i])-1)
            dp[i+1][True][j] += dp[i][False][j]
            

        # i桁目まで等しい状態からi+1桁目も等しい状態のとき
        if int(n[i]) != 0:
            dp[i+1][False][j+1] = dp[i][False][j]
        else:
            dp[i+1][False][j] = dp[i][False][j]

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

Submission status: Accepted

Solution code:
import numpy as np
N = input()
K = int(input())
keta = len(N)
dp = np.zeros((keta + 1, 2, K + 1), dtype=np.int64)

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

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

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

Submission status: Accepted

Solution code:
## ABC154E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


M = 10**9+7 # 出力の制限
N = 100 # 必要なテーブルサイズ

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 



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

dp0 = [[0]*(k+1) for _ in range(l+1)] # i桁目まででNより小さく、非零がjの個数
dp1 = [[0]*(k+1) for _ in range(l+1)] # i桁目でNと同じで、非零がjの個数
dp1[0][0] = 1

if k>l:
    ans = 0
else:
    for i in range(1,l+1):
        for j in range(k+1):
            c = int(n[i-1])
            if j>=1:
                dp0[i][j] += 9 * dp0[i-1][j-1]
            dp0[i][j] += dp0[i-1][j]            
            if c>=1:
                dp0[i][j] += dp1[i-1][j]
                if j>=1:
                    dp0[i][j] += (c-1) * dp1[i-1][j-1]
                
            if c==0:
                dp1[i][j] += dp1[i-1][j]
            elif j>=1:
                dp1[i][j] += dp1[i-1][j-1]
                
ans = dp0[l][k] + dp1[l][k]
print(ans)

Submission status: Accepted

Solution code:
n = str(input())
k = int(input())
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(len(n)):
    for j in range(k+1):
        if n[i] == "0":
            dp[i+1][0][j] = dp[i][0][j]
            dp[i+1][1][j] = dp[i][1][j]
            if j > 0:
                dp[i+1][1][j] += dp[i][1][j-1]*9
        else:
            dp[i+1][1][j] = dp[i][0][j] + dp[i][1][j]
            if j > 0:
                dp[i+1][0][j] = dp[i][0][j-1]
                dp[i+1][1][j] += dp[i][0][j-1] * (int(n[i])-1) + dp[i][1][j-1] * 9
  # print(dp)
print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = LSI()
K = I()
dp = FILL3(0,len(N)+1,K+1,2)
dp[0][0][0] = 1
for i in range(len(N)):
    for j in range(K+1):
        for k in range(2):
            m = N[i]
            max_d = 9 if k else m
            for d in range(max_d+1):
                k_ = k or d<max_d
                j_ = j + (d!=0)
                if j_ > K:
                    continue
                dp[i+1][j_][k_]+=dp[i][j][k]
print(dp[len(N)][K][0] + dp[len(N)][K][1])