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 itertools

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

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

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        #print(v)
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += (int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s >= v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                else:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += max(0,int(N[0])-1)*9*9

    print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        #print(v)
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += max(0,int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s >= v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                else:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += max(0,int(N[0])-1)*9*9

    print(ans)

Submission status: Accepted

Solution code:
import itertools

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


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

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        #print(v)
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += max(0,int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s == v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                elif not0s < v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
                    #ans += int(N[0])*int(N[v[1]])*9
                else:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += max(0,int(N[0])-1)*9*9

    print(ans)

Submission status: Accepted

Solution code:
import itertools

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


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

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        #print(v)
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 == v[1]:
                ans += max(0,int(N[0])-1)*9 + int(N[v[1]])
            elif not0 < v[1]:
                ans += int(N[0])*9
            else:
                ans += max(0,int(N[0])-1)*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s == v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                elif not0s < v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
                    #ans += int(N[0])*int(N[v[1]])*9
                else:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += max(0,int(N[0])-1)*9*9

    print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
n=int(input())
k=int(input())
@lru_cache(None)
def F(x,y):  #xという数字に対して0出ない数字がyこのモノの個数
    if x<10:
        if y==1:
            return x
        elif y==0:
            return 1
        else:
            return 0
    else:
        res=0
        q,r=divmod(x,10)
        res+=F(q,y)  #最後の桁が0
        if y>=1:
            res+=r*F(q,y-1) #最後の桁が1-r
            res+=(9-r)*F(q-1,y-1) #最後がr+1,,,9
        return res
print(F(n,k))

Submission status: Accepted

Solution code:
def nCk(n, k):
    if n < k:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2:
        return n * (n - 1) // 2
    else:
        return n * (n - 1) * (n - 2) // 6


def solve(N, K):
    if K == 0:
        return 1

    M = len(str(N))
    hd, tl = divmod(N, 10 ** (M - 1))

    res = nCk(M - 1, K) * (9 ** K)
    if hd == 0:
        return res

    res += solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    return res


N, K = map(int, open(0).read().split())
print(solve(N, K))

Submission status: Accepted

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

def one(n):
    l = len(str(n))
    ans = 9 * (l-1)
    ans += n//(10**(l-1))
    return ans

def two(n):
    l = len(str(n))
    if l == 1:
        ans = 0
    elif l == 2:
        ans = (n//10-1) *9 + n%10
    else:
        ans =   81 * (l-1) * (l-2) // 2
        t = n % (10**(l-1))
        ans += one(t) + one(10**(l-1)-1)* (n// (10**(l-1))-1)
    return ans

def three(n):
    l = len(str(n))
    if l <= 2:
        ans = 0
    elif l == 3:
        ans = (n//100-1) * two(99) + two( n % 100 )
    else:
        ans = 729 * (l-1) * (l-2) * (l-3) // 6
        t = n % (10**(l-1))
        ans += two(t) + two(10**(l-1)-1)* (n// (10**(l-1))-1)
    return ans

if k == 1:
    ans = one(n)
if k == 2:
    ans = two(n)
if k == 3:
    ans = three(n)

print(ans)

Submission status: Accepted

Solution code:
def nCk(n, k):
    if k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2:
        return n * (n - 1) // 2
    else:
        return n * (n - 1) * (n - 2) // 6


def solve(N, K):
    if N < K:
        return 0

    if K == 0:
        return 1

    M = len(str(N))
    hd, tl = divmod(N, 10 ** (M - 1))

    res = nCk(M - 1, K) * (9 ** K)
    if hd == 0:
        return res

    res += solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    return res


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

print(solve(N, K))

Submission status: Accepted

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

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


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:  # 0以外が一個増える
                    nj += 1
                if nj > K:  # これ以上0以外使えないとき
                    continue
                if k == 0:  # そこまでの桁はNと一致しているとき
                    if d > nd:  # Nを超えてしまう
                        continue
                    if d < nd:  # N以下確定である
                        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:
n = input()
k = int(input())

def case1(x):
    return (len(x) - 1) * 9 + int(x[0])

def case2(x):
    if (len(x) < 2):
        return 0
    ret = (len(x) - 1) * (len(x) - 2) // 2 * 81
    ret += case1('9' * (len(x) - 1)) * (int(x[0]) - 1)
    for i in range(1, len(x)):
        if x[i] != '0':
            ret += case1(x[i:])
            break
    return ret

def case3(x):
    if (len(x) < 3):
        return 0
    ret = (len(x) - 1) * (len(x) - 2) * (len(x) - 3) // 6 * 729
    ret += case2('9' * (len(x) - 1)) * (int(x[0]) - 1)
    for i in range(1, len(x)):
        if x[i] != '0':
            ret += case2(x[i:])
            break
    return ret

if k == 1:
    print(case1(n))
elif k == 2:
    print(case2(n))
else:
    print(case3(n))

Submission status: Accepted

Solution code:
def nCk(n, k):
    if k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2:
        return n * (n - 1) // 2
    else:
        return n * (n - 1) * (n - 2) // 6


def solve(N, K):
    if N == 0 and K > 0:
        return 0

    if K == 0:
        return 1

    M = len(str(N))
    hd, tl = divmod(N, 10 ** (M - 1))

    res = nCk(M - 1, K) * (9 ** K)
    if hd == 0:
        return res

    res += solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    return res


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

print(solve(N, K))

Submission status: Accepted

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

# dp = [頭からi桁目][未満フラグ][これまでに出てきた0以外の数]
dp = [[[0 for i in range(K+1)] for f in range(2)] for n in range(len(str(N)))]

# init
Ni = int(str(N)[0])
# 頭が0
dp[0][1][0] = 1
if Ni == 1:
    dp[0][0][1] = 1  # 頭が1
else:
    dp[0][0][1] = 1  # 頭がNi
    dp[0][1][1] = Ni-1  # 頭が1~(Ni-1)

# print(dp[0])
for i in range(1,len(str(N))):
    Ni = int(str(N)[i])
    for k in range(K+1):
        # N未満であることが確定している
        dp[i][1][k] += dp[i-1][1][k]  # 0
        if k < K:
            dp[i][1][k+1] += dp[i-1][1][k]*9  # 1~9

        # N未満であることが確定していない(頭からi桁目までがNと一致している)
        if Ni == 0:
            # 0を選ぶしかない。未満フラグは立たない
            dp[i][0][k] += dp[i-1][0][k]
        elif Ni == 1:
            # 0 未満フラグが立つ
            dp[i][1][k] += dp[i-1][0][k]
            # 1 未満フラグが立たない
            if k < K:
                dp[i][0][k+1] += dp[i-1][0][k]
        else:
            # 0 未満フラグが立つ
            dp[i][1][k] += dp[i-1][0][k]
            # 1~(Ni-1) 未満フラグが立つ
            if k < K:
                dp[i][1][k+1] += dp[i-1][0][k]*(Ni-1)
            # Ni 未満フラグが立たない
            if k < K:
                dp[i][0][k+1] += dp[i-1][0][k]
    # print(dp[i])
print(dp[-1][0][K]+dp[-1][1][K])

Submission status: Accepted

Solution code:
def nCk(n, k):
    if k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2:
        return n * (n - 1) // 2
    else:
        return n * (n - 1) * (n - 2) // 6


def solve(N, K):
    if N == 0 and K > 0:
        return 0

    if K == 0:
        return 1

    M = len(str(N))
    hd, tl = divmod(N, 10 ** (M - 1))

    res = solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    if M > K:
        res += nCk(M - 1, K) * (9 ** K)

    return res


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

print(solve(N, K))

Submission status: Accepted

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

l = len(n)
n = int(n)

ans=0

def one(n):
    l = len(str(n))
    ans = 9 * (l-1)
    ans += n//(10**(l-1))
    return ans

def two(n):
    l = len(str(n))
    ans = 0
    if l == 1:
        return 0
    elif l == 2:
        ans = (n//10-1) *9 + n%10
        return ans
    else:
        ans +=   81 * (l-1) * (l-2) // 2
        # print(81*5*4/2)
        # print(ans)
        t = n % (10**(l-1))
        ans += one(t) + one(10**(l-1)-1)* (n// (10**(l-1))-1)
        return ans

def three(n):
    l = len(str(n))
    ans = 0
    if l <= 2:
        # print(n)
        return ans
    elif l == 3:
        ans = (n//100-1) * two(99) + two( n % 100 )
        return  ans
    else:
        ans = 729 * (l-1) * (l-2) * (l-3) // 6
        t = n % (10**(l-1))
        ans += two(t) + two(10**(l-1)-1)* (n// (10**(l-1))-1)
        return ans
    return ans

if k == 1:
    ans = one(n)
if k == 2:
    ans = two(n)
if k == 3:
    ans = three(n)

if l <= 3 and n != one(n) + two(n) + three(n):
    print(one(n),two(n),three(n))
    print("Error!")

print(ans)

# 100000 ~ 314159 

# print()

# n=9 k=1:9
# n=99 k=1:18 k=2:81=81*2C2
# n=999 k=1:27 k=2:81*3=243,81*(3C2) k=3:9^3=729 = 729*3C3
# n=9999 k=1:9*4, k=2:81*4C2, K=3:729*4C3=

# k=2, 1,2,6,10,15,

# n=515 nの桁数:d=3 10^(d-1)=100 515/100=5 100,200,300,400,500 18+5=23
# n=515, k=2:101~109,110,120,130~190,201~209
# n=250,18,
# k=2,1001-1009,1010,1020...1090,1100,1200..1900 27*9=243
# k=2を求めるよりも、k<=2を求めてからk=1を求める方が簡単か? そんなこともないか

Submission status: Accepted

Solution code:
def nlog(n):
    for i in range(200):
        if n<10**i:
            return i-1
n=int(input())
k=int(input())

ns=nlog(n)
n1=n//10**int(ns)
#print(ns,n1,n1*10**ns)

if k==1:
    icnt=0
    for i in range(0,ns+1):
        for i1 in range(1,10):
            x=i1*10**i
            if x<=n:
                icnt=icnt+1
    print(icnt)
elif k==2:
    icnt=0
    for i in range(0,ns):
        for j in range(i+1,ns+1):
            for i1 in range(1,10):
                for j1 in range(1,10):
                    x=i1*10**i+j1*10**j
                    if x<=n:
                        icnt=icnt+1
    print(icnt)
elif k==3 and n<=122:
    icnt=0
    print(icnt)
elif k==3 and n>=123:
    icnt=0
    for i in range(0,ns):
        for j in range(i+1,ns+1):
            for i1 in range(1,10):
                for j1 in range(1,10):
                    x=n1*10**ns+i1*10**i+j1*10**j
                    if x<=n:
                        icnt=icnt+1

    icnt=icnt+int((n1-1)*ns*(ns-1)/2*9*9)
    icnt=icnt+int(ns*(ns-1)*(ns-2)/6*9*9*9)

    print(icnt)

Submission status: Accepted

Solution code:
from itertools import product
from collections import defaultdict
def resolve():
    s = input()
    K = int(input())
    dp = defaultdict(int)
    dp[0, 0, 0] = 1
    for i, less, k in product(range(len(s)), (0, 1), range(K+1)):
        max_d = 9 if less else int(s[i])
        max_d = 0 if k == K else max_d
        for d in range(max_d+1):
            less_ = less or d < max_d
            k_ = k + 1 if d > 0 else k
            dp[i + 1, less_, k_] += dp[i, less, k]
    print(sum(dp[len(s), less, K] for less in (0, 1)))
resolve()

Submission status: Accepted

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

dp1 = [ [ i+1 for i in range(9) ] for i in range(201)]
dp2 = [ [ 0 for i in range(9) ] for i in range(201)]
dp3 = [ [ 0 for i in range(9) ] for i in range(201)]

for i in range(200):
    for j in range(9):
        if j == 0:
            dp1[i+1][j] = dp1[i][-1] + 1
        else:
            dp1[i+1][j] = dp1[i+1][j-1] + 1

for i in range(200):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(200):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(100):
    for j in range(9):
        if j == 0:
            dp3[i+1][j] = dp3[i][-1] + 81 * i*(i-1)//2
        else:
            dp3[i+1][j] = dp3[i+1][j-1] + 81 * (i+1) * i //2


def solve(s, x):
    if s == "0":
        return 0
    elif s[0] == "0":
        return solve(s[1:], x)

    if x == 1:

        return  dp1[len(s)-1][int(s[0]) - 1]
    elif x == 2:
        if len(s) < 2:
            return 0
        return  dp2[len(s)-1][int(s[0]) - 1] + solve(s[1:], 1)
    elif x == 3:
        if len(s) < 3:
            return 0
        return  dp3[len(s)-1][int(s[0]) - 1] + solve(s[1:], 2)

print(solve(n, k))

Submission status: Accepted

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

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

def getMiman(X):
  if X>0:
    return X-1
  else:
    return 0

x0=int(N[0])
dp[0][0][0]=0
dp[0][1][0]=1
dp[0][0][1]=1
dp[0][1][1]=getMiman(x0)

for i in range(1,keta):
  x=int(N[i])
  dp[i][0][0]=0
  dp[i][1][0]=1
  for j in range(1,K+1):
    dp[i][0][j]=dp[i-1][0][j-1]*(x!=0)+dp[i-1][0][j]*(x==0)
    dp[i][1][j]=dp[i-1][0][j-1]*getMiman(x)+dp[i-1][0][j]*(x!=0)+dp[i-1][1][j-1]*9+dp[i-1][1][j]*1
  
print(dp[keta-1][0][K]+dp[keta-1][1][K])

Submission status: Accepted

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

def solve(num_str, k, smaller):
    if num_str == "" and k > 0:
        return 0
    if k == 0 or num_str == "":
        return 1

    elif smaller:
        keta = len(num_str)
        if k == 1:
            return keta * 9
        elif k == 2:
            return keta * (keta-1)//2 * 9 * 9
        else:
            return keta * (keta-1) * (keta -2)//6 * 9 * 9 * 9
    else:   
        num = int(num_str)
        num_str = str(num_str)
        top = int(num_str[0])
        if top:
            zero = solve(num_str[1:], k, True)
            non_zero = solve(num_str[1:], k-1, True) * (top - 1)
            just = solve(num_str[1:], k-1, False)
            return zero + non_zero + just
        else:
            return solve(num_str[1:], k, False)
print(solve(str(N), K, False))

Submission status: Accepted

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

res = 0
if K == 1:
    for i in range(1,10):
        for j in range(len(str(N))):
            if i*10**j <= N:
                res += 1
if K == 2:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for j1 in range(len(str(N))-1):
                for j2 in range(len(str(N))-1-j1):
                    if i1*10**(j1+j2+1)+i2*10**j2 <= N:
                        res += 1

if K == 3:
    for j1 in range(len(str(N))-2-1):
        for j2 in range(len(str(N))-2-1-j1):
            for j3 in range(len(str(N))-2-1-j1-j2):
                res += 1
    res = res * (9**3)
    
    for j1 in range(len(str(N))-2):
        for j2 in range(len(str(N))-2-j1):
            j3 = len(str(N))-2-j1-j2-1
            for i1 in range(1,10):
                for i2 in range(1,10):
                    for i3 in range(9,0,-1):
                        if i1*10**(j1+j2+j3+2)+i2*10**(j2+j3+1)+i3*10**+j3 <= N:
                            res += i3
                            break

print(res)

Submission status: Accepted

Solution code:
from math import factorial

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


def ncr(n, r):
    if n < r:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)


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


def k2(n):
    if n < 10:
        return 0
    s = str(n)
    res = ncr(len(s)-1, 2) * 9 * 9
    res += (int(s[0]) - 1) * k1(10 ** (len(s) - 1) - 1) + k1(int(s[1:]))
    return res


def k3(n):
    s = str(n)
    res = ncr(len(s)-1, 3)*9*9*9
    res += (int(s[0]) - 1) * k2(10 ** (len(s) - 1) - 1) + k2(int(s[1:]))
    return res


kf = [k1, k2, k3]
print(kf[K-1](N))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

N=raw_input()
K=input()

dp=defaultdict(lambda: 0)  #未満T or F , i桁目, 0でない数値がちょうどk個

l=len(N)

for i in range(l):
    x=int(N[i])
    i+=1
    if i==1:
        if x==1:
            dp[("T",i,0)]=1
            dp[("F",i,1)]=1
        else:
            dp[("T",i,0)]=1
            dp[("T",i,1)]=x-1
            dp[("F",i,1)]=1
    else:
        for k in range(K+1):
            #未満:Trueの場合
            dp[("T",i,k)]+=dp[("T",i-1,k)]      #k桁目の数字pが0の場合
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*9  #k桁目の数字pが0以外の場合。1-9までの9個の数を使用して良い
            #未満:Falseの場合
            if 0<x:
                dp[("T",i,k+1)]+=dp[("F",i-1,k)]*(x-1) #k桁目の数字pが0<p<xなのは、x-1通り。この場合は未満の方に移動
                dp[("T",i,k)]+=dp[("F",i-1,k)]  #k桁目の数字pが0の場合は1通り。この場合は未満の方に移動
                dp[("F",i,k+1)]+=dp[("F",i-1,k)]*1 #k桁目の数字p=xの場合はゼロでない数字の個数が1個増える
            else: #k桁の目の数字xが0の場合
                dp[("F",i,k)]+=dp[("F",i-1,k)]*1
        
print dp[("T",l,K)]+dp[("F",l,K)]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

N=raw_input()
K=input()

dp=defaultdict(lambda: 0)  #未満T or F , i桁目, 0でない数値がちょうどk個

l=len(N)

for i in range(l):
    x=int(N[i])
    i+=1
    if i==1:
        if x==1:
            dp[("T",i,0)]=1
            dp[("F",i,1)]=1
        else:
            dp[("T",i,0)]=1
            dp[("T",i,1)]=x-1
            dp[("F",i,1)]=1
    else:
        for k in range(K+1):
            #未満:Trueの場合
            dp[("T",i,k)]+=dp[("T",i-1,k)]      #k桁目の数字pが0の場合
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*9  #k桁目の数字pが0以外の場合。1-9までの9個の数を使用して良い
            #未満:Falseの場合
            if 0<x:
                dp[("T",i,k+1)]+=dp[("F",i-1,k)]*(x-1) #k桁目の数字pが0<p<xなのは、x-1通り。この場合は未満の方に移動
                dp[("T",i,k)]+=dp[("F",i-1,k)]  #k桁目の数字pが0の場合は1通り。この場合は未満の方に移動
                dp[("F",i,k+1)]+=dp[("F",i-1,k)]*1 #k桁目の数字p=xの場合はゼロでない数字が1個増える
            else: #k桁の目の数字xが0の場合
                dp[("F",i,k)]+=dp[("F",i-1,k)]*1
        
print dp[("T",l,K)]+dp[("F",l,K)]

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import log10, ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = input()
K = INT()
L = len(N)
dp = [[[0]*2 for _ in range(4)] for _ in range(L+1)]
dp[0][0][0] = 1
for i in range(L):
	for j in range(4):
		for k in range(2):
			nd = int(N[i])
			for d in range(10):
				ni, nj, nk = i+1, j, 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[L][K][0] + dp[L][K][1]
print(ans)

Submission status: Accepted

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

suu = []
for i in range(L):
    suu.append(int(str(N)[i]))

DP_1 =[[0 for k in range(L+2)] for i in range(L+1)]
DP_2 =[[0 for k in range(L+2)] for i in range(L+1)]
DP_2[0][0] = 1
for i in range(L):
    for k in range(L+1):
        DP_1[i+1][k] = DP_1[i][k] + DP_1[i][k-1] * 9 
        if suu[i]:
            DP_1[i+1][k] += DP_2[i][k] + DP_2[i][k-1] * max(suu[i] - 1, 0)
            DP_2[i+1][k] = DP_2[i][k-1]
        else:
            DP_2[i+1][k] = DP_2[i][k]
print(DP_1[L][K]+ DP_2[L][K])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = input()
n = len(S)
K = int(input())
dp = [[[0]*2 for _ in range(K+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):          # i:桁
    for j in range(K+1):    # j:非0の数
        for k in range(2):  # k:0->nと同じ数,1->nより小さい数
            nd = int(S[i])  #nd:nのi桁
            for d in range(10):
                ni, nj, nk = i+1, j, k
                if d != 0: nj += 1      # 非0の数が増える
                if nj > K: continue     # 非0の数がKを超えたら計算不要
                if k == 0:              # ここまでnと同じ場合
                    if d > nd: continue # nより大きくなるのでダメ
                    if d < nd: nk = 1   # nより小さくなるのでkは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:

import numpy as np

N=input()
K=input()
dp=np.zeros((len(str(N))+10,len(str(N))+10,2))
dp=dp.tolist()


x0=int(N[0])
dp[0][0][0]=1


for i in range(0,len(N),1):
    for j in range(0,4,1):
        for k in range(0,2,1):
            nd=int(N[i])
            for d in range(0,10,1):
                ni=i+1
                nj=j
                nk=k
                if not(d==0):
                    nj=nj+1
                if ((k==0)and(d<nd)):
                    nk=1
                if (not(nj>int(K)))and(not((k==0)and(d>nd))):
                    dp[ni][nj][nk]=dp[ni][nj][nk]+dp[i][j][k]


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

Submission status: Accepted

Solution code:
# 0でない数字がちょうどK個
S = input().strip()
K = int(input())
N = len(S)

'''
桁DP
dp[i][j][k] := 
i桁目まで使って
j個の0ではない数値を使って
k=0:i桁目までSと一致
  1:S未満(以下？)
'''
dp = [[[0]*2 for _ in range(K+1)] for _ in range(101)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(K+1):
        for k in range(2):
            nd = int(S[i])
            # 0-9まで調べていく
            for d in range(10):
                ni, nj, nk = i+1, j, k
                if d > 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    elif d != nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sys
from pprint import pprint
import math

INF = float("inf")
  
def solve(N: str, K: int):
    M = len(N)
    DP = [[[0]*2 for __ in range(K+1)] for _ in range(M+1)]
    Nstr = N
 
    DP[0][0][False] = 1
 
    for i in range(M):
        DP[i+1][0][True] = 1
        DP[i+1][0][False] = 0
        for k in range(K):
            DP[i+1][k+1][True] = DP[i][k][True]*9 + DP[i][k+1][True]*1
            if int(Nstr[i]) != 0:
                DP[i+1][k+1][True] += DP[i][k+1][False]
                DP[i+1][k+1][True] += DP[i][k][False]*(int(Nstr[i])-1)
            if int(Nstr[i]) == 0:
                DP[i+1][k+1][False] = DP[i][k+1][False]
            else:
                DP[i+1][k+1][False] = DP[i][k][False]
    print(DP[M][K][True]+DP[M][K][False])
    # print(*DP, sep="\n")
 
    return
 
 
if __name__ == '__main__':
 
    n = sys.stdin.readline().strip()
    k = int(sys.stdin.readline().strip())
     
    solve(n, k)

Submission status: Accepted

Solution code:
from math import factorial


def cmb(n, r):
    if n-r < 0 or r < 0:
        return 0
    else:
        return factorial(n) // (factorial(r) * factorial(n - r))


def solve(n, k):
    if k < 0:
        return 0

    if n == [] or sum(n) == 0:
        if k == 0:
            return 1
        else:
            return 0

    for i in range(len(n)):
        if n[i] != 0:
            break

    n = n[i:]

    l = len(n)
    ans = 0

    # n-1桁からKこ取る
    tmp1 = (9**k)*cmb(l-1, k)

    # 最上位から1つ（最上位の数以外）とる。
    tmp2 = (n[0]-1)*(9**(k-1))*cmb(l-1, k-1)

    # 最上位からその数をとる。
    tmp3 = solve(n[1:], k-1)

    ans = tmp1 + tmp2 + tmp3
    return int(ans)


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

print(solve(n, k))

Submission status: Accepted

Solution code:
from math import factorial


def cmb(n, r):
    if n-r < 0 or r < 0:
        return 0
    else:
        return factorial(n) // (factorial(r) * factorial(n - r))


def solve(n, k):
    if n == [] or sum(n) == 0:
        if k == 0:
            return 1
        else:
            return 0

    for i in range(len(n)):
        if n[i] != 0:
            break

    n = n[i:]

    l = len(n)
    ans = 0

    # n-1桁からKこ取る
    tmp1 = (9**k)*cmb(l-1, k)

    # 最上位から1つ（最上位の数以外）とる。
    tmp2 = (n[0]-1)*(9**(k-1))*cmb(l-1, k-1)

    # 最上位からその数をとる。
    if k > 1:
        tmp3 = solve(n[1:], k-1)
    elif k == 1:
        if len(n) == 1:
            tmp3 = 1
        else:
            tmp3 = solve(n[1:], k-1)
    else:
        tmp3 = 0

    ans = tmp1 + tmp2 + tmp3
    return int(ans)


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

print(solve(n, k))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

s=int(input()); n=len(str(s))
k=int(input())
S=[int(i) for i in str(s)]
dpl=[[0]*(k+1) for i in range(n+1)]
dpj=[[0]*(k+1) for i in range(n+1)]
dpj[0][0]=1
for i in range(n):
    for j in range(k+1):
        dpj[i+1][j] += dpj[i][j]*(S[i]==0)
        dpl[i+1][j] += dpl[i][j] + dpj[i][j]*(S[i] >= 1)
        if j+1 < k+1:
            dpj[i+1][j+1] += dpj[i][j]*(S[i] > 0)
            dpl[i+1][j+1] += dpl[i][j]*9 + dpj[i][j]*max(0,S[i]-1) 

print(dpl[n][k]+dpj[n][k])
# print(dpl)
# print(dpj)