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 = input()
k = int(input())
dp = [[[0 for i in range(k+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(k+1):
      for i in range(10):
        if b ==1:
          if c ==k:  
            if i == 0:
              dp[a+1][1][c] += dp[a][1][c]
          else:
            if i == 0:
              dp[a+1][1][c] += dp[a][1][c]
            else:
              dp[a+1][1][c+1] += dp[a][1][c]
        else:
          if int(n[a]) > i:
            if c == k:
              if i == 0:
                dp[a+1][1][c] += dp[a][0][c]
            else:
              if i == 0:
                dp[a+1][1][c] += dp[a][0][c]
              else:
                dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i:
            if c == k:
              if i == 0:
                dp[a+1][0][c] += dp[a][0][c]
            else:
              if i == 0:
                dp[a+1][0][c] += dp[a][0][c]
              else:
                dp[a+1][0][c+1] += dp[a][0][c]
            
            
print(dp[-1][0][-1] + dp[-1][1][-1])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
dp = [[[0 for i in range(len(n)+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if int(n[a]) > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if int(n[a]) > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if int(n[a]) == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
if len(n) == 1:
  if k == 1:
    print(int(n))  
  if k >= 2:
      print(0)
else:
  print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Accepted

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

dp = [[[0,0] for _ in range(K+1)] for _ in range(L+1)]
dp[0][0][0] = 1
for i,c in enumerate(S):
    c = int(c)
    for k in reversed(range(K+1)):
        for d in range(10):
            nk = k + (d>0)
            if nk > K: continue
            dp[i+1][nk][1] += dp[i][k][1]
            if d > c: continue
            dp[i+1][nk][int(c>d)] += dp[i][k][0]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:
s,k=input(),int(input())
n=[int(i) for i in s]
l=len(s)
dp=[[[0]*(k+1),[0]*(k+1)] for i in range(l+1)]
dp[0][0][0]=1
for i in range(l):
    for smaller in range(2):
        for x in range(10 if smaller else n[i]+1):
            if x==0:
                for y in range(k+1):
                    dp[i+1][smaller or x<n[i]][y]+=dp[i][smaller][y]
            else:
                for y in range(k):
                    dp[i+1][smaller or x<n[i]][y+1]+=dp[i][smaller][y]
print(dp[-1][0][-1]+dp[-1][1][-1])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
K = ir()

@lru_cache(None)
def solve(N, K):
    assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0
    q, r = divmod(N, 10)
    ret = 0
    if K > 0:
        ret += solve(q, K-1) * r
        ret += solve(q-1, K-1) * (9-r)
    ret += solve(q, K)  # 一桁目が0
    return ret

answer = solve(N, K)
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from functools import lru_cache

n, k = map(int, read().split())


@lru_cache()
def check(n, k):
    if n < 10:
        if k == 0:
            return 1
        if k == 1:
            return n
        return 0
    a, b = divmod(n, 10)
    cnt = 0
    if k >= 1:
        cnt += check(a, k - 1) * b
        cnt += check(a - 1, k - 1) * (9 - b)
    cnt += check(a, k)
    return cnt


print(check(n, k))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = list(map(int, sr()))
K = ir()
dp_dec = [0] * (K+1)
dp_reserved = [0] * (K+1)
dp_reserved[0] = 1
for x in N:
    prev = dp_dec[:]
    # 0の場合はそのままの値
    for k in range(K):
        dp_dec[k+1] += prev[k] * 9  # 1-9の場合
    if x > 0:
        for k in range(K+1):
            dp_dec[k] += dp_reserved[k]  # 0の場合
            if k < K:
                dp_dec[k+1] += dp_reserved[k] * (x - 1)  # 1-9の場合
        dp_reserved[1:] = dp_reserved[:-1]
        dp_reserved[0] = 0

answer = dp_dec[K] + dp_reserved[K]
print(answer)
# 07

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n = s_in()
k = n_in()

res = 0
d = len(n)

def comb(a,b):
    if b == 0:
        return 1
    if b == 1:
        return a
    if b == 2:
        return a*(a-1)//2
    if b == 3:
        return (a)*(a-1)*(a-2)//6

    return 0
    

# 手前まで完全一致でii桁以降でl回非ゼロの時の場合の数
def calc(i, l):
    m = int(n[i])

    if i == d-1:
        if l == 0:
            if m == 0:
                return 1
            else:
                return 0
        elif l == 1:
            if m == 0:
                return 0
            else:
                return m
        else:
            return 0
            
        
    if m == 0:
        return calc(i+1, l)
    else:
        tmp = calc(i+1, l-1) # i桁めがmの場合
        tmp += (m-1)*comb(d-i-1, l-1)*int(9**(l-1)) # 1..(m-1)
        tmp += comb(d-i-1,l)*int(9**l)

        return tmp

print(calc(0,k))

Submission status: Accepted

Solution code:
def calc(n, k):
    length = len(n)
    dp = [[[0]*(k + 1) for _ in range(2)] for _ in range(length+1)]
    dp[0][0][0] = 1
    for i in range(length):
        max_digit = int(n[i])
        for flag_less in range(2):
            for non_zero in range(4):
                range_digit = 9 if flag_less else max_digit
                for d in range(range_digit+1):
                    flag_less_next = 0
                    non_zero_next = non_zero
                    if flag_less == 1 or d < max_digit:
                        flag_less_next = 1
                    if d != 0:
                        non_zero_next = non_zero + 1
                    if non_zero_next < k + 1:
                        dp[i+1][flag_less_next][non_zero_next] += dp[i][flag_less][non_zero]
    return dp[length][0][k]+dp[length][1][k]

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

print(calc(n, k))

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int,read().split())

@lru_cache(None)
def F(N, K):
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    q, r = divmod(N, 10)
    ret = 0
    if K >= 1:
        ret += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    ret += F(q, K)
    return ret

print(F(N, K))

Submission status: Accepted

Solution code:
# 桁DP
def solve(S, K):
    L = len(S)
    # dp[決定した桁数][未満フラグ][０以外の数字を使った個数]
    dp = [[[0 for _ in range(4)] for _ in range(2)] for _ in range(101)]
    dp[0][0][0] = 1
    for i in range(L):  # 今見ている桁
        D = int(S[i])
        for j in range(2):  # 未満フラグ(0 or 1)
            for k in range(4):  # ０以外の数字を使った個数が0~3
                for d in range(10 if j else D + 1):
                    cnt = k
                    if d != 0:
                        cnt += 1
                    if cnt > K:
                        continue
                    dp[i + 1][j or (d < D)][cnt] += dp[i][j][k]

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


def main():
    n = int(input())
    K = int(input())
    print(solve(str(n), K))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

S = list(input())
K = int(input())
N = len(S)

# print(S)

# dp[i][j][k]
dp = [[[0] * 2 for _ in range(K+2)] for _ in range(N+1)]

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

# 上の桁から調べていく
for i in range(1, N + 1):
    for j in range(K + 1):
        for k in range(2):
            for num in range(10):
                if num == 0:
                    inc = 0
                else:
                    inc = 1
                # N未満が確定していれば0-9の全ての遷移が可能なので加える
                if k == 1:
                    dp[i][j+inc][k] += dp[i - 1][j][k]
                else:
                    if num < int(S[i-1]):
                        # k = 1が確定
                        dp[i][j + inc][1] += dp[i - 1][j][k]
                    elif num == int(S[i-1]):
                        # k = 0のまま
                        dp[i][j + inc][0] += dp[i - 1][j][k]

# print(dp)

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

Submission status: Accepted

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

string = str(N)
digits = len(string)

#dp[i][j][k]=と同じ桁数の整数で上からi桁目までで0でない数字がj個あるものの個数
#k=0: i桁目まで見てN未満が確定, k=1: 未確定
dp = [[[0]*2 for _ in range(K+1)] for __ in range(digits+1)]
#初期状態
dp[0][0][1] = 1

for i in range(digits):
    d = int(string[i])
    ni = i+1
    for j in range(K+1):
        for k in range(2):
            for nd in range(10):
                nk = 1 if k == 1 and nd == d else 0
                if k == 1 and nd > d: break

                nj = j + (1 if nd != 0 else 0)
                if nj > K: continue

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

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

Submission status: Accepted

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def search(d, cnt, isEq):
    if d == len(N):
        return 1 if cnt == K else 0

    n = int(N[d])

    if isEq and n == 0:
        return search(d + 1, cnt, isEq)

    if isEq:
        ret = 0
        ret += search(d + 1, cnt, False)
        for _ in range(1, n):
            ret += search(d + 1, cnt + 1, False)
        ret += search(d + 1, cnt + 1, True)
        return ret

    return search(d + 1, cnt, False) + search(d + 1, cnt + 1, False) * 9

print(search(0, 0, True))

Submission status: Accepted

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

n = len(s)

dp = [[[0]*2 for i in range(4)] for j 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])
            for d in range(10):
                ni = i+1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if k == 0:
                    if d > nd:
                        continue
                    elif d < nd:
                        nk = 1
                    else:
                        pass
                if 0 <= nj <= 3:
                    dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = input().strip("\n")
    K = int(input())
    dig = len(N)
    DP = [[0] * (K + 1) for _ in range(dig)]
    DP[0][0] = 1
    DP[0][1] = int(N[0]) - 1
    for i in range(1, dig):
        DP[i][1] = 9
        if N[i] != "0": 
            DP[i][0] = DP[i-1][0] + 1
            if DP[i-1][0] <= K: DP[i][DP[i-1][0]] += 1
            if DP[i-1][0] <= K - 1: DP[i][DP[i-1][0] + 1] += int(N[i]) - 1     
        else: DP[i][0] = DP[i-1][0]
        for j in range(1, K): DP[i][j+1] += DP[i-1][j] * 9
        for j in range(1, K + 1): DP[i][j] += DP[i - 1][j]
    if DP[dig - 1][0] == K: DP[dig - 1][K] += 1
    print(DP[dig - 1][K])
    #print(DP)

            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
    S = input()
    N = len(S)
    K = int(input())
    dp = [[[0]*5 for j in range(2)] for i in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(2):
            for k in range(4):
                lim = (9 if j else int(S[i]))
                for d in range(lim + 1):
                    # print(i, j, lim, d, j or d < lim)
                    dp[i+1][j or d < lim][k + int(d != 0)] += dp[i][j][k]
    print((dp[N][0][K]+dp[N][1][K]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = input()
k = int(input())
dp = [[0] * (3 + 1) for i in range(len(n))]
dp[0][1] = int(n[0])
cnt = 1
for i in range(1, len(n)):
  m = int(n[i])
  if cnt == 1:
    dp[i][1] = 9 + dp[i - 1][1]
    dp[i][2] = (dp[i - 1][1] - 1) * 9 + dp[i - 1][2] + m
    dp[i][3] = dp[i - 1][2] * 9 + dp[i - 1][3]
  elif cnt == 2:
    dp[i][1] = 9 + dp[i - 1][1]
    dp[i][2] = dp[i - 1][1] * 9 + dp[i - 1][2]
    dp[i][3] = (dp[i - 1][2] - 1) * 9 + dp[i - 1][3] + m
  else:
    dp[i][1] = 9 + dp[i - 1][1]
    dp[i][2] = dp[i - 1][1] * 9 + dp[i - 1][2]
    dp[i][3] = dp[i - 1][2] * 9 + dp[i - 1][3]
  if m != 0:
    cnt += 1
print(dp[len(n) - 1][k])

Submission status: Accepted

Solution code:
N=str(input())
n=len(N)
K=int(input())
dp0=[[0]*(K+1) for _ in range(n+1)]
dp1=[[0]*(K+1) for _ in range(n+1)]
for l in range(1,n+1):
  dp0[l][0]=1
dp1[0][0]=1
for i in range(n):
  for j in range(K):
    if N[i]=='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]=dp0[i][j]*9+dp0[i][j+1]+dp1[i][j]*(int(N[i])-1)+dp1[i][j+1]
      dp1[i+1][j+1]=dp1[i][j]
print(dp0[n][K]+dp1[n][K])

Submission status: Accepted

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

# defnition
N_bin = str(N)
digit_len_N = len(N_bin)
DP = [[[0]*(K+2) for _ in range(2)] for _ in range(digit_len_N+1)]
# DP[i][j][k]は、上位i桁目までで、(j==0 ?Nと同じになる可能性あり:必ずNより小さくなる)の時に、0以外の数がkこ出現する、数字の数


# initialize
DP[0][0][0] = 1

# solve with けたDP
for digit in range(digit_len_N):
    max_digit = int(N_bin[digit])
    for smaller in range(2):  # smaller=0?Nと同じになる可能性あり:Nより小さいの確定
        for k in range(K+1):
            cand_digits = max_digit+1 if smaller == 0 else 10  # 小さい確定なら0~9の全部が候補
            for next in range(cand_digits):
                if next == max_digit and smaller == 0:  # Nと同じになる可能性を残しつつ
                    if next == 0:  # 0のときは,kの値が増えないので特別扱い
                        DP[digit+1][0][k] += DP[digit][0][k]
                    else:
                        DP[digit+1][0][k+1] += DP[digit][0][k]
                else:  # ここで、Nより必ず小さい道に行く
                    if next == 0:  # 0のときは,kの値が増えないので特別扱い
                        DP[digit+1][1][k] += DP[digit][smaller][k]
                    else:
                        DP[digit+1][1][k+1] += DP[digit][smaller][k]
print(DP[-1][0][K]+DP[-1][1][K])

Submission status: Accepted

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

# defnition
N_bin = str(N)
bit_len_N = len(N_bin)
DP = [[[0]*(K+2) for _ in range(2)] for _ in range(bit_len_N+1)]
# Kは0でない数の数
# smaller=0はboarder

DP[0][0][0] = 1

# solve with けたDP
for bit in range(bit_len_N):
    max_digit = int(N_bin[bit])
    for smaller in range(2):
        for k in range(K+1):
            cand_digits = max_digit+1 if smaller == 0 else 10
            for next in range(cand_digits):
                if next == max_digit and smaller == 0:
                    if next == 0:
                        DP[bit+1][0][k] += DP[bit][0][k]
                    else:
                        DP[bit+1][0][k+1] += DP[bit][0][k]
                else:
                    if next == 0:
                        DP[bit+1][1][k] += DP[bit][smaller][k]
                    else:
                        DP[bit+1][1][k+1] += DP[bit][smaller][k]
print(DP[-1][0][K]+DP[-1][1][K])

Submission status: Accepted

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

Submission status: Accepted

Solution code:

def f(i,k):#i桁目がnum未満
    if i == 0:
        return 0
    num = int(s[-i])
    if k == 0:
        if num ==0:return 0
        else: return 1
    if num==0:
        return 0
    return (num-1)* ncr(i-1,k-1)*9**(k-1)+ncr(i-1,k)*9**k


def g(i,k):#i桁目がnum
    if i == 0:
        if k==0:return 1
        else:return 0
    num = int(s[-i])
    if k == 0:
        if num ==0:return 1
        else:return 0

    if num==0:
        return f(i-1,k) +g(i-1,k)
    else:
        return f(i-1,k-1) + g(i-1,k-1)



def ncr(n,r):##　n>>r の場合のncr　O(r) r>nなら0
    x = 1
    y = 1
    for i in range(r):
        x*=(n-i)
        y*=(i+1)
    return x//y

s = input()
k = int(input())
l= len(s)
print(f(l,k)+g(l,k))

Submission status: Accepted

Solution code:
n=list(input())
N=len(n)
k=int(input())
dp1=[[0 for i in range(k+1)] for j in range(N+1)]
dp2=[[0 for i in range(k+1)] for j in range(N+1)]
dp1[0][0]=1
for i in range(1,N+1):
  x=int(n[i-1])
  
  if i!=N and x!=0:
    for j in range(k+1):
      if j==0:
        dp2[i][j]=dp1[i-1][j]+dp2[i-1][j]
      else:
        dp1[i][j]=dp1[i-1][j-1]
        dp2[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*(x-1)+dp2[i-1][j]+dp2[i-1][j-1]*9
  
  elif i!=N and x==0:
    for j in range(k+1):
      if j==0:
        dp1[i][j]=dp1[i-1][j]
        dp2[i][j]=dp2[i-1][j]
      else:
        dp1[i][j]=dp1[i-1][j]
        dp2[i][j]=dp2[i-1][j]+dp2[i-1][j-1]*9
  
  elif i==N and x!=0:
    for j in range(k+1):
      if j==0:
        dp2[i][j]=dp1[i-1][j]+dp2[i-1][j]
      else:
        dp2[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*x+dp2[i-1][j]+dp2[i-1][j-1]*9
  
  else:
    for j in range(k+1):
      if j==0:
        dp2[i][j]=dp2[i-1][j]
      else:
        dp2[i][j]=dp1[i-1][j]+dp2[i-1][j]+dp2[i-1][j-1]*9

print(dp2[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 in range(L):
    d = int(n[i])
    for j in [0, 1]:
        for k in range(K + 1):
            if j == 0:
                dp[i + 1][j][k] += dp[i][j][k]
                dp[i + 1][j][k + 1] += dp[i][j][k] * 9
            else:
                if d > 0:
                    dp[i + 1][0][k] += dp[i][j][k]
                    dp[i + 1][0][k + 1] += dp[i][j][k] * (d - 1)
                    dp[i + 1][1][k + 1] += dp[i][j][k]
                else:
                    dp[i + 1][1][k] += dp[i][j][k]


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

Submission status: Accepted

Solution code:

from functools import lru_cache

@lru_cache(maxsize=10000)
def calc(n, k):
    # print(n, k)

    if n < 10:
        if k > 1:
            # print('1:return 0')
            return 0
        elif k == 1:
            # print('2:return ' + str(n))
            return n
        else:
            return 1

    else:
        if k == 0:
            # print('5:return ')
            return 1#calc(n // 10, k)
        else:
            # print('6:return ')
            return calc(n // 10, k - 1) * (n % 10) + calc(n // 10 - 1, k - 1) * (9 - n % 10) + calc(n // 10, k)

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

print(calc(n, k))

Submission status: Accepted

Solution code:
def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**3):
        fact.append(fact[-1]*i % mod)

    def inv_n(n):
        return pow(n, mod-2, mod)

    def nCr(n, r, mod=10**9+7):
        return inv_n(fact[n-r]*fact[r] % mod)*fact[n] % mod

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

    m = len(n)
    ans2 = 0
    if len(n)-n.count("0") == k:
        ans2 = 1
    for i in range(m):
        s = n[i]
        if s != "0":
            if k >= 0 and m-i-1 >= k:
                ans2 += nCr(m-i-1, k)*pow(9, k)
            k -= 1
            if k >= 0 and m-i-1 >= k:
                ans2 += (int(n[i])-1)*nCr(m-i-1, k)*pow(9, k)
    print(ans2)


main()

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
dp = [[[0]*2 for _ in range(4)] for _ in range(105)]
# dp[i][j][k]:上からi桁まで決めて0でない数字をj個用いた数字で
# k = 0の時Nと一致,k=1の時N未満が確定
# 求める答えはdp[len(str(N))][K][0] + dp[len(str(N))][K][1]
# k=0からk=1の遷移が不可逆

dp[0][0][0] = 1
length = len(str(N))
for i in range(length):
    for j in range(4):
        for k in range(2):
            next_digit = int(str(N)[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 next_digit < d:
                        continue
                    if next_digit > d:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
ans = dp[length][K][0] + dp[length][K][1]
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N = iip(False)
    K = iip(False)
    ret = solve(N, K)
    print(ret)

def solve(N, K):

    strn = str(N)

    A = []
    B = []

    for i in range(len(strn), 0, -1):
        if strn[len(strn)-i] != "0":
            A.append(int(strn[len(strn)-i]))
            B.append(i)


    if K == 1:
        return 9*(B[0]-1) + A[0]


    if K == 2:
        if len(strn) < 2:
            return 0
        ret = 0
        ret += (B[0]-1) * (B[0]-2) // 2 * (9**2) #桁数がmaxじゃない場合
        ret += (A[0]-1) * 9 * (B[0]-1) #桁数がmaxで先頭桁がmax以外の場合
        if len(B) >= 2 and len(A) >= 2:
            ret += (B[1]-1) * 9 + A[1] #先頭桁がmaxの場合
        return ret

    ret = 0
    ret += (B[0] - 1) * (B[0] - 2) * (B[0] - 3) // 6 * 9**3 #桁数がmaxじゃない場合
    ret += (A[0] - 1) * (B[0] - 1) * (B[0] - 2) // 2 * 9**2 #桁数がmaxで先頭桁がmaxじゃない場合

    #以下、桁数はmaxで先頭桁はmaxとする
    if len(strn) < 3:
        return 0
    if len(B) >= 2:
        ret += (B[1]-1) * (B[1]-2) // 2 * 9**2 #有効2桁目の桁数がmaxじゃない場合
    if len(B) >= 2 and len(A) >= 2:
        ret += (A[1] - 1) * (B[1]-1) * 9 #有効2桁目の桁数がmaxで数字がmaxじゃない場合
    if len(B) >= 3 and len(A) >= 3:
        ret += (B[2] - 1) * 9 + A[2] #有効2桁目,3桁目がmaxの場合
    return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = list(str(input()))
l = len(n)
for i in range(l):
	n[i] = int(n[i])
k = int(input())
dp0 = [[0 for _ in range(4)] for _ in range(l+1)]
dp1 = [[0 for _ in range(4)] for _ in range(l+1)]
dp0[1] = [1, n[0]-1, 0, 0]
dp1[1] = [0, 1, 0, 0]
for i in range(2,l+1):
	for j in range(4):
		p = n[i-1]
		if j == 0:
			if p == 0:
				dp0[i][j] = dp0[i-1][j]
				dp1[i][j] = dp1[i-1][j]
			else:
				dp0[i][j] = 1
				dp1[i][j] = 0
		elif p == 0:
			dp1[i][j] = dp1[i-1][j]
			dp0[i][j] = dp0[i-1][j] + 9 * dp0[i-1][j-1]
		else:
			dp1[i][j] = dp1[i-1][j-1]
			dp0[i][j] = dp0[i-1][j] + 9 * dp0[i-1][j-1] + dp1[i-1][j] + (p-1) * dp1[i-1][j-1]
print(dp0[l][k] + dp1[l][k])

Submission status: Accepted

Solution code:
N=int(input())
K=int(input())
#桁の数字を取得
dig=[]
n=N
while n>0:
  dig.append(n%10)
  n//=10
a=dig[-1]
digit=len(dig)

dp=[[0 for _ in range(digit)] for _ in range(3)]

dp[0][0]=dig[0]
for i in range(1,digit):
  if dig[i]==0:
    dp[0][i]=dp[0][i-1]
  else:
    dp[0][i]=dig[i]+9*i

for i in range(1,digit):
  if dig[i]==0:
    dp[1][i]=dp[1][i-1]
  else:
    dp[1][i]=dp[0][i-1]+(dig[i]-1)*9*i+81*i*(i-1)//2
    
for i in range(1,digit):
  if dig[i]==0:
    dp[2][i]=dp[2][i-1]
  else:
    dp[2][i]=(dp[1][i-1]  #i桁目がギリギリの場合
              +(dig[i]-1)*81*i*(i-1)//2 #i桁目を使う場合
              +729*i*(i-1)*(i-2)//6) #i桁目を使わない場合
print(dp[K-1][digit-1])

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(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])
            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(dp[N][K][0] + dp[N][K][1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)


def solve(N: int, K: int):
    NL = list(map(int, N))

    useMaxDigits = [[0 for i in range(K+1)] for j in range((len(N)+1))]
    noUseMaxDigits = [[0 for i in range(K+1)]
                      for j in range((len(N)+1))]
    useMaxDigits[0][0] = 1
    for digit in range(1, len(N)+1):
        D = NL[digit-1]
        # Use Max continueingly
        if D != 0:
            for i in range(1, K+1):
                useMaxDigits[digit][i] = useMaxDigits[digit-1][i-1]
            for i in range(0, K+1):
                noUseMaxDigits[digit][i] = useMaxDigits[digit-1][i]
        else:
            for i in range(0, K+1):
                useMaxDigits[digit][i] = useMaxDigits[digit-1][i]

        # Use non max
        for i in range(0, K+1):
            # if use zero
            noUseMaxDigits[digit][i] += noUseMaxDigits[digit-1][i]
        for i in range(1, K+1):
            noUseMaxDigits[digit][i] += noUseMaxDigits[digit-1][i-1]*9
        for i in range(1, K+1):
            noUseMaxDigits[digit][i] += useMaxDigits[digit -
                                                     1][i-1]*max(0, D-1)
    print(useMaxDigits[-1][-1]+noUseMaxDigits[-1][-1])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from math import factorial

def main():
  s = list(map(int, input().strip()))
  k = int(input())
  dp = []
  dp.append([[0]*(len(s)+1) for _ in range(k+1)])
  dp.append([[0]*(len(s)+1) for _ in range(k+1)])
  dp[0][0][0] = 1
  
  for i, c in enumerate(s):
    for j in range(k+1):
        for d in range(10):
          nj = j
          if d != 0:
            nj+=1
          if nj > k:
            continue
            
          if d < c:
            dp[1][nj][i+1] += dp[0][j][i]
          if d == c:
            dp[0][nj][i+1] += dp[0][j][i]
          dp[1][nj][i+1] += dp[1][j][i]
            
  print(dp[0][k][len(s)]+dp[1][k][len(s)])

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import math
import itertools
n=int(input())
k=int(input())
def comb(n,k):
    return len(list(itertools.combinations(range(n), k)))
x=str(n)
m=len(x)
ans=0
for i in range(1,m):
    ans+=(comb(i-1,k-1)*(9**k))
if k==1:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            ans+=1
elif k==2:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            for j in range(m-1):
                for a in range(1,10):
                    if i*(10**(m-1))+a*(10**(j))<=n:
                        ans+=1
                    else:
                        break
        else:
            break
else:
    po=[10**i for i in range(m)]
    for i in range(1,10):
        if i*po[m-1]<=n:
            for j in range(m-1):
                for a in range(1,10):
                    if i*po[m-1]+a*po[j]<=n:
                        for b in range(j):
                            for c in range(1,10):
                                ans+=(i*po[m-1]+a*po[j]+c*po[b]<=n)
                    else:
                        break
        else:
            break
print(ans)