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 = int(input())
K = int(input())
strN = [int(n) for n in str(N)]
keta_N = len(strN)

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


#dp[keta][k][smaller]

for keta in range(keta_N):
    Nb = strN[keta]
    for k in range(4):
        for smaller in range(2):
            if smaller == 1:
                dp[keta + 1][k][smaller] += dp[keta][k][smaller]
                dp[keta + 1][k + 1][smaller] += dp[keta][k][smaller] * 9
            if smaller == 0:
                if Nb == 0:
                    dp[keta + 1][k][smaller] += dp[keta][k][smaller]
                if Nb == 1:
                    dp[keta + 1][k][smaller + 1] += dp[keta][k][smaller]
                    dp[keta + 1][k+1][smaller] += dp[keta][k][smaller]
                if Nb >= 2:
                    dp[keta + 1][k][smaller + 1] += dp[keta][k][smaller]
                    dp[keta + 1][k+1][smaller + 1] += dp[keta][k][smaller] * (Nb - 1)
                    dp[keta+1][k+1][smaller] += dp[keta][k][smaller]

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

Submission status: Accepted

Solution code:
N = input()
n = [ int(x) for x in list(N)]

K = int(input())
nl = len(N)
cnt = 0

if K == 1:
    cnt += n[0]   + (nl-1) * 9
elif K == 2 and nl >= 2:
    if nl == 2:
        cnt += (n[0]-1) * 9 + n[1]
    if nl > 2:
        cnt += (nl-1) * (nl-2) * 9 * 9 // 2
        cnt += (n[0]-1) * 9 * (nl-1)
        for i in range(1,nl):
            if n[i] > 0:
                cnt += n[i] + (nl - i -1) * 9
                break
elif K == 3 and  nl >= 3:
    if nl == 3:
        cnt += (n[0]-1) * 9 * 9
        cnt += (n[1]-1) * 9 + n[2]
    elif nl > 3:
        cnt += (nl-1) * (nl-2) * (nl-3) // 6 * 9 * 9 * 9
        cnt += (n[0]-1) * (nl-1) * (nl-2) //2 * 9 * 9
        for i in range(1,nl):
            if n[i] > 0:
                cnt += (nl-i-1) * (nl-i-2) // 2 * 9 * 9
                cnt += (n[i]-1) * (nl-i-1) * 9
                for j in range(i+1,nl):
                    if n[j] > 0:
                        cnt += (nl-j-1) * 9
                        cnt += n[j]
                        break
                break
print (cnt)

Submission status: Accepted

Solution code:
digits = [int(c) for c in input()]
n = len(digits)
m = int(input())

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

for i, digit in enumerate(digits):
    for j in range(m + 1):
        for k in range(2):
            for d in range(10 if k else digit + 1):
                dp[i + 1][j + (d > 0)][k or (d < digit)] += dp[i][j][k]

print(sum(dp[n][m]))

Submission status: Accepted

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

# dp[i][j][k] : i桁目まで見て、非ゼロがj回出て、
# k=0ならそれまでの桁はNと一致、k=1なら既にN以下が決定してる
dp = [[[0] * 2 for _ in range(4)] for _ in range(105)]
dp[0][0][0] = 1

# i, j, kは遷移前のdpの状態
# ni, nj, nkは遷移先のdpの状態
for i in range(N):
    nd = int(S[i])
    for j in range(4):
        for k in range(2):
            for d in range(10):
                ni = i + 1
                nj = j
                nk = k
                if d != 0:  # 非ゼロを使うのでjを1つ増やす
                    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:
import sys

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

N = sr()
K = ir()
length = len(N)
top = int(N[0])
dp_dec = [[0] * 4 for _ in range(length)] #decided
dp_pen = [[0] * 4 for _ in range(length)] #pending
dp_dec[0][1] = (top-1)
dp_dec[0][0] = 1
dp_pen[0][1] = 1
for i in range(1, length):
    cur = int(N[i])
    if cur == 0:
        dp_pen[i] = dp_pen[i-1][:] #右端に0
    else:
        for k in range(1, 4):
            dp_pen[i][k] = dp_pen[i-1][k-1] #右端にcur

    dp_dec[i] = dp_dec[i-1][:] #0が右端に加わった場合
    for j in range(1, 4):
        dp_dec[i][j] += dp_dec[i-1][j-1] * 9 #1~9が右端に加わった場合
        if cur > 0:
            dp_dec[i][j] += dp_pen[i-1][j-1] * (cur-1) + dp_pen[i-1][j] * 1 # 右端にcur以下の数が加わった場合と0が加わった場合

answer = dp_dec[length-1][K] + dp_pen[length-1][K]
print(answer)

Submission status: Accepted

Solution code:
import sys

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

N = sr()
K = ir()
length = len(N)
top = int(N[0])
dp_dec = [[0] * 4 for _ in range(length)]
dp_pen = [[0] * 4 for _ in range(length)]
dp_dec[0][1] = (top-1)
dp_dec[0][0] = 1
dp_pen[0][1] = 1
#print(dp_dec)
for i in range(1, length):
    cur = int(N[i])
    if cur == 0:
        dp_pen[i] = dp_pen[i-1][:] #右端に0
    else:
        for k in range(1, 4):
            dp_pen[i][k] = dp_pen[i-1][k-1] #右端にcur

    dp_dec[i] = dp_dec[i-1][:] #0が右端に加わった場合
    for j in range(1, 4):
        #print('for', i, j, dp_dec)
        dp_dec[i][j] += dp_dec[i-1][j-1] * 9 #1~9が右端に加わった場合
        if cur > 0:
            dp_dec[i][j] += dp_pen[i-1][j-1] * (cur-1) + dp_pen[i-1][j]
    #print(i, dp_dec)

answer = dp_dec[length-1][K] + dp_pen[length-1][K]
print(answer)

Submission status: Accepted

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

def solve(n,k):
    if k==0: return 1
    if n < 10:
        return n if k==1 else 0
    if n < 100 and k == 3:
        return 0
    m,d = divmod(n,10)
    ret = d * solve(m,k-1)
    ret += (9-d)*solve(m-1,k-1)
    ret += solve(m,k)
    return ret

print(solve(N,K))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    K=int(input())
    str_N=str(N)
    M=len(str(N))
    dp=[[[0]*2 for _ in range(K+1)] for _ in range(M+1)]
    dp[0][0][0]=1
    for keta in range(M):
        dp[keta+1][0][1]=dp[keta][0][0]+dp[keta][0][1]
        for k in range(K):
            dp[keta+1][k+1][1]=dp[keta][k][0]*(max(int(str_N[keta])-1,0))+dp[keta][k][1]*9+dp[keta][k+1][1]
            if int(str_N[keta])==0:
                dp[keta+1][k+1][0]=dp[keta][k+1][0]
            else:
                dp[keta+1][k+1][0]=dp[keta][k][0]
                dp[keta+1][k+1][1]+=dp[keta][k+1][0]
    ans=sum(dp[M][K])
    print(ans)
                

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=input()
K=int(input())
l=len(N)
dp=[[0]+[1]*l]+[[0]*(l+1) for i in range(K)]
dp2=[[1]+[0]*l]+[[0]*(l+1) for i in range(K)]
for i,n in enumerate(N):
    n=int(n)
    for j in range(K):
        dp[j+1][i+1]=dp[j][i]*9+dp[j+1][i]+(dp2[j][i]*(n-1)+dp2[j+1][i] if n>0 else 0)
        dp2[j+1][i+1]=dp2[j][i] if n>0 else dp2[j+1][i]
print(dp[-1][-1]+dp2[-1][-1])

Submission status: Accepted

Solution code:

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



dp = [[[0 for _ in range(2)] for _ in range(K+1)] for _ in range(len(str(N))+1)]
# 頭から0桁目まで決めて、0以外の数が0個既に使われている時、i桁目までの部分がNより小さいのは0の一通り
dp[0][0][0] = 1


"""
N = 987654として、

（１）3桁目までみたときに、987より小さくなるdp[3][j][1]への派生は
・87から870を作るような、dp[2][j][1]から
・98から980みたいなのがあるから、dp[2][j][0]から。ただし、Nの３桁目が0だと、今作ってる３桁目までの数字98＊が980未満になれないので、その場合はスキップ
↑↑↑ここまではi桁目に0を使うパターン↑↑↑
↓↓↓i桁目に0以外を使うパターン↓↓↓
まだ使える0以外の個数がのこっているとき、
・87から871~879の９パターンに派生する形なので、dp[i][j-1][1] から派生するのが9通りなので * 9 して足す（0以外の値を一つ消化する）
・98から981~986への派生なので、dp[i][j-1][0] * (digit[i] - 1) (例でいうところの７未満の値を使える)　（0以外の値を一つ消化する）

（２）3桁目までみたときに、987と一致するようなdp[3][j][0]への派生は
・もし３桁目が０なら、98から980への派生があるので、dp[i][j][0]から派生できる
・もし３桁目が０ではないのなら、98から987へ派生し、一つ0以外の数字を消化するので、dp[i][j-1][0]から派生


みたいに考えていく。
"""

for i in range(len(str(N))):
    digit = int(str(N)[i])
    for j in range(K+1):
        # i桁目までがNのそこまでより小さい場合、i-1桁目までもNのi-1桁目までより小さいことが確定するから、
        # i-1 -> iへの派生を入れる（from 厳密に小さい to 厳密に小さい）
        dp[i+1][j][1] += dp[i][j][1]

        # i-1桁目までがNのi-1桁目までより小さくなく（一致し）、Nのi桁目が０であれば、作っている数字のi桁目が０になる
        if digit == 0:
            # 厳密に小さくなれないので（from 厳密に小さくない to 厳密に小さくない）
            dp[i+1][j][0] += dp[i][j][0]
        else:
            """
            314159で、31OXXXかつNの3桁目までより小さいパターンは、31XXXXから派生
            """
            # （from 厳密に小さくない（一致する） to 厳密に小さい）
            dp[i+1][j][1] += dp[i][j][0]
        
        # 先頭になんか0以外の数字を入れて、残りがまだ0以外の数字を入れる必要があるとき
        if j-1 >= 0:
            # 0以外のなんかの値を使ったので j-1 -> j かつ  * 9（０以外をいれる）
            dp[i+1][j][1] += dp[i][j-1][1] * 9
            if digit != 0:
                # i桁目が一致する（Nのiまでより小さくならない）パターンについて、直前の場合の数を足す
                dp[i+1][j][0] += dp[i][j-1][0]
                # i桁目までが、Nのそれまでより小さくなるパターンについて、i桁目ではdより小さい値をとれる
                dp[i+1][j][1] += dp[i][j-1][0] * (digit-1)

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

Submission status: Accepted

Solution code:
N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    if p<q : return 0
    else: return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
def mi(i):
    if i==0:
        return 0
    else:
        return i-1
def zero(i):
    if int(n[i])==0:
        return 0
    else:
        return 1
if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
    if K==1:ans+=int(n[0])
    elif K==2:
        x=0
        i=1
        b=0
        bs=0
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            if (x==1) or (i==len(n)-1):
                break
            i+=1
        ans+=mi(int(n[0]))*(a-1)*9+mi(bs)*9+b
    elif a==3 : ans+=mi(int(n[0]))*81*(combi(a-1,2))+9*mi(int(n[1]))+int(n[2])
    else:
        x=0
        i=1
        b=0
        bs=0
        c=0
        cs=0
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            elif (int(n[i])!=0) and (x==1):
                c=int(n[i])
                cs=a-i
                x+=1
            if (x==2) or (i==len(n)-1):
                break
            i+=1
        ans+=mi(int(n[0]))*81*(combi(a-1,2))+combi(bs-1,2)*81+9*(a-2)*mi(b)+c+mi(cs)*9

print(ans)

Submission status: Accepted

Solution code:

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


def nCr(n,r):
  if n < 0 or r < 0 or n < r: return 0
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n
  
  # 分子のn*(n-1)*...がr個分続くやつ
  numerator = [n-r+k+1 for k in range(r)]
  # 分母：r!=r*(r-1)*...*3*2の要素
  denominator = [k+1 for k in range(r)]
  
  # 分母の要素で割れる部分を割っていく部分
  for p in range(2, r+1):
    # 分母は1,2,3,...rのようになっており、1は意味がないのでスキップした形か
    pivot = denominator[p-1]
    if pivot > 1:
      # 分子のX番目と分母のX-offset番目が共通の約数を持つということだと思う。piv分ずれているのだから、pivの倍数というところか
      offset = (n-r) % p
      for k in range(p-1, r, p):
        # 約分できる要素について割る
        numerator[k - offset]  /= pivot
        denominator[k] /= pivot
        
  ret = 1
  for k in range(r):
    if numerator[k] > 1: ret *= int(numerator[k])
      
  return ret


dp = [[[0 for _ in range(2)] for _ in range(K+1)] for _ in range(len(str(N))+1)]
# 頭から0桁目まで決めて、0以外の数が0個既に使われている時、i桁目までの部分がNより小さいのは0の一通り
dp[0][0][0] = 1


for i in range(len(str(N))):
    digit = int(str(N)[i])
    for j in range(K+1):
        # i桁目までがNのそこまでより小さい場合、i-1桁目までもNのi-1桁目までより小さいことが確定するから、
        # i-1 -> iへの派生を入れる（from 厳密に小さい to 厳密に小さい）
        dp[i+1][j][1] += dp[i][j][1]

        # i-1桁目までがNのi-1桁目までより小さくなく（一致し）、Nのi桁目が０であれば、作っている数字のi桁目が０になる
        if digit == 0:
            # 厳密に小さくされないので（from 厳密に小さくない to 厳密に小さくない）
            dp[i+1][j][0] += dp[i][j][0]
        else:
            """
            314159で、31OXXXかつNの3桁目までより小さいパターンは、31XXXXから派生
            """
            # （from 厳密に小さくない（一致する） to 厳密に小さい）
            dp[i+1][j][1] += dp[i][j][0]
        
        # 先頭になんか0以外の数字を入れて、残りがまだ0以外の数字を入れる必要があるとき
        if j-1 >= 0:
            # 0以外のなんかの値を使ったので j-1 -> j かつ  * 9（０以外をいれる）
            dp[i+1][j][1] += dp[i][j-1][1] * 9
            if digit != 0:
                # i桁目が一致する（Nのiまでより小さくならない）パターンについて、直前の場合の数を足す
                dp[i+1][j][0] += dp[i][j-1][0]
                # i桁目までが、Nのそれまでより小さくなるパターンについて、i桁目ではdより小さい値をとれる
                dp[i+1][j][1] += dp[i][j-1][0] * (digit-1)

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

Submission status: Accepted

Solution code:
N=int(input())
K=int(input())
dp1=[[0 for _ in range(4)] for _ in range(101)]
dp2=[[0 for _ in range(4)] for _ in range(101)]
dp1[0][0]=1
for i in range(1, 101):
    dp1[i][0]=1
    for j in range(1, 4):
        dp1[i][j]=dp1[i-1][j-1]*9+dp1[i-1][j]
dp2[0][1]=1
for i in range(1, 101):
    dp2[i][1]=dp1[i][1]+1
    dp2[i][2]=dp1[i][2]
    dp2[i][3]=dp1[i][3]
ans=0
i=len(str(N))-1
cnt=0
while i>=0:
    k=int(str(N)[len(str(N))-1-i])
    if k==0:
        i-=1
        continue
    ans+=dp2[i][K-cnt]
    cnt+=1
    if K-cnt<0:
        break
    ans+=dp1[i][K-cnt]*(k-1)
    i-=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = list(map(int,input()))
    K = int(input())
    if len(N) < K :
        print(0)
    else:
        print(dfs(N, 0, K))
def test(N,K):
    return dfs(list(map(int,str(N))),0,K)

def comb(N, K):
    if N < K:
        return 0
    if K == 0:
        return 1
    elif K == 1:
        return N
    elif K == 2:
        return N * (N - 1) // 2
    elif K == 3:
        return N * (N - 1) * (N - 2) // 6


def dfs(N, pos, rest):
    if rest == 0:
        return 1
    if pos >= len(N):
        return 0
    ans = 0
    for i in range(10):
        if N[pos] > i:
            if i == 0:
                ans += comb(len(N) - pos - 1, rest) * (9**rest)
            else:
                ans += comb(len(N) - pos - 1, rest - 1) * (9 ** (rest-1))
        elif N[pos] == i :
            if i == 0 :
                ans += dfs(N, pos+1, rest)
            else :
                ans += dfs(N, pos+1, rest - 1)
        else:
            break
    return ans
if __name__ == "__main__":
    main()

Submission status: Accepted

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

N_ = str(N)
n = len(N_)

dp = [[[0]*2 for i in range(5)] for j in range(110)]

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

for i in range(n):
  for j in range(4):
    for k in range(2):
      nd = int(N_[i])
      for d in range(10):
        ni = i+1
        nj = j
        nk = k
        if d != 0:
          nj += 1
        if nj >3:
          continue
        if k == 0:
          if d > nd:
            continue
          elif d < nd:
            nk = 1
          else:
            pass
        dp[ni][nj][nk] += dp[i][j][k]
        
print(sum(dp[n][K]))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
K = inp()
s = list(str(n))
l = len(s)

dp = [[[0 for _ in range(2)] for j in range(4)] for i in range(l+5)]
dp[0][0][0] = 1

for i in range(l):
    nd = int(s[i])
    # print(nd)
    for j in range(4):
        for k in range(2):
            for d in range(10):
                ni = i+1; nj = j; nk = k
                if d>0: nj += 1
                if nj >= 4: continue

                if k == 0:
                    if d < nd: nk += 1
                    elif d > nd: continue
                dp[ni][nj][nk] += dp[i][j][k]
# print(dp)
print(sum(dp[l][K]))

Submission status: Accepted

Solution code:
def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret /= i+1
  return ret

def top(N,K):
  if K == 0:
    return 1
  L = len(N)
  ans = 0
  if L < K:
    return 0
  else:
    ans += nCr(L-1,K) * 9 ** K

    u = int(N[0])
    z = N.count('0')
    o = N.count('1')
    f = 0
    if z + o == L:
      f = 1
    if f == 0:
      ans += (u - 1) * nCr(L-1,K - 1) * 9 ** (K - 1)
      if L == 1:
        return ans + 1
      else:
        return ans + top(str(int(N[1:])),K - 1)
    else:
      if len(str(int(N[1:]))) != 1:
        return ans + top(str(int(N[1:])),K - 1)
      else:
        if o >= K:
          return ans + 1
        else:
          return ans

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

print(int(top(N,K)))

Submission status: Accepted

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


def ketadp(X):
    X = '0' + str(X)
    dp = [[[0] * 4 for _ in range(2)] for _ in range(len(X))]
    dp[0][0][0] = 1
    for i in range(len(X) - 1):
        for j in range(2):
            for d in range(10 if j else int(X[i + 1]) + 1):
                if d == 0:
                    for k in range(4):
                        dp[i + 1][j or d < int(X[i + 1])][k] += dp[i][j][k]
                else:
                    for k in range(3):
                        dp[i + 1][j or d < int(X[i + 1])][k + 1] += dp[i][j][k]

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


print(ketadp(N))

Submission status: Accepted

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

# F(N,K) ... N以下の整数で0でない数字がちょうどK個あるものの個数

from functools import lru_cache
import sys
sys.setrecursionlimit(1 << 25)


@lru_cache(None)
def F(N, K):
    '''N以下でちょうど0以外がK回出てくる (0以外を特にカウントする)'''
    # 終了条件
    assert N > -1
    if K < 0:
        return 0
    if N < 10:
        if K == 0:
            return 1  # '0'でないものが0個の状況、一桁ならば0は必ず0から始まる
        if K == 1:
            return N  # 3だったら1,2,3と'0'でないものが存在する。
        return 0  # それ以外はありえない。

    # 桁dp
    q, r = divmod(N, 10)
    ret = 0
    for d in range(10):
        # d=0のとき、これは必ずF(q,K)の通りの数足される
        if d == 0:
            ret += F(q, K)
        else:  # d=0のとき以外はKは一つ消費される
            # d>rのときF(q-1,K-1)から寄与が来る
            if d > r:
                ret += F(q - 1, K - 1)
            else:
                ret += F(q, K - 1)
    return ret


print(F(N, K))

Submission status: Accepted

Solution code:
# coding: utf-8
N=int(input())
K=int(input())

lN=len(str(N))

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

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

for i in range(lN):
    num=int(str(N)[i])
    for j in range(K+1):
        if num==0:
            dp[i+1][0][j] = dp[i][0][j]
        else:
            if j==0:
                dp[i+1][0][j] = 0
            else:
                dp[i+1][0][j] = dp[i][0][j-1]
        
        if j==0:
            dp[i+1][1][j] = 1
        else:
            if num==0:
                dp[i+1][1][j] = dp[i][1][j-1]*9 + dp[i][1][j]*1
            else:
                dp[i+1][1][j] = dp[i][1][j-1]*9 + dp[i][1][j]*1 + dp[i][0][j-1]*(num-1) + dp[i][0][j]*1

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

Submission status: Accepted

Solution code:
def run():
  N = list(map(int, list(input())))
  K = int(input())
  Nlen = len(N)
  dp = [[[0]*(K+2) for _ in range(2)] for n in range(Nlen+1)]
  dp[0][0][0] = 1
  for nlen in range(Nlen):
    dN = N[nlen]
    for d in range(10):
      for j in range(2):
        for k in range(K+2):
          flagj = j or d < dN
          if (flagj == 0) and (d > dN): continue
          flagk = min(K+1, k+(d != 0))
          dp[nlen+1][flagj][flagk] += dp[nlen][j][k]
  print(dp[-1][0][K]+dp[-1][1][K])
  
if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1

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

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

Submission status: Accepted

Solution code:
import itertools

def read():
    N = str(input().strip())
    K = int(input().strip())
    return N, K

def solve(N, K):
    L = len(N)
    D = [int(N[i]) for i in range(L)]
    dp0 = [[0 for k in range(K+1)] for i in range(L+1)]
    dp1 = [[0 for k in range(K+1)] for i in range(L+1)]
    
    dp0[0][0] = 1
    for i in range(L):
        for k in range(K+1):
            if k < K and D[i] > 0:
                dp0[i+1][k+1] += dp0[i][k]
                for d in range(1, D[i]):
                    dp1[i+1][k+1] += dp0[i][k]
            if D[i] == 0:
                dp0[i+1][k] += dp0[i][k]
            else:
                dp1[i+1][k] += dp0[i][k]
            if k < K:
                for d in range(1, 10):
                    dp1[i+1][k+1] += dp1[i][k]
            dp1[i+1][k] += dp1[i][k]
    return dp0[L][K] + dp1[L][K]


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

Solution code:
N = list(map(int,list(input())))
K = int(input())
#print(N)

def main(k,p):
    l = len(k)
    x = 9 ** p###先頭桁が0
    for i in range(p):
        x *= max(l - 1 - i,0)
    for i in range(p):
        x //= (i+1)
    y = (k[0] - 1)*(9**(p-1))###先頭桁が1以上k[0]-1以下
    for i in range(p-1):
        y *= max(l - 1 - i,0)
    for i in range(p-1):
        y //= (i+1)
    ##以下, 先頭がk[0]
    i = 1
    while i < l-1 and k[i] == 0 :
        i += 1
    #print("i=",i)
    if p == 1:
        z = 1
    elif i == l-1 and k[i]==0:
        z = 0
    else:
        z = main(k[i:],p-1)
    #print(k,x,y,z)
    return (x+y)+z

if len(N) < K:
    print(0)
else:
    print(main(N,K))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
K = I()

S = str(N)
L = len(S)

# dp[i][x][f] : i桁目まで見て，0以外がx個ある総数
#              （f=1:N未満が確定，f=0:未確定）
dp = [[[0]*2 for _ in range(K+1)] for _ in range(L)]
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = int(S[0])-1

for i in range(1,L):
    for x in range(K+1):
        if S[i] == '0':
            dp[i][x][0] = dp[i-1][x][0]
            dp[i][x][1] = dp[i-1][x][1]
            if x >= 1:
                dp[i][x][1] += 9*dp[i-1][x-1][1]
        else:
            dp[i][x][1] = dp[i-1][x][0] + dp[i-1][x][1]
            if x >= 1:
                dp[i][x][0] = dp[i-1][x-1][0]
                dp[i][x][1] += 9*dp[i-1][x-1][1] + (int(S[i])-1)*dp[i-1][x-1][0]

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

Submission status: Accepted

Solution code:
x = int(input())
X = [int(i) for i in str(x)]
y = int(input())
dp = [[[0] * 2 for i in range(4)] for j in range(len(str(x))+1)]
dp[0][0][0] = 1

for i in range(len(str(x))):
  for j in range(4):
    for m in range(2):
      for n in range(10):
        nj = j + 1 if n != 0 else j
        if nj == 4: continue
        nm = m        
        if X[i] > n and m == 0:
          nm = 1
        if X[i] < n and m == 0:
          continue
        dp[i+1][nj][nm] += dp[i][j][m]

print(dp[len(X)][y][0]+dp[len(X)][y][1])

Submission status: Accepted

Solution code:
import sys

def comb(n, r):
    if r > n or r < 0: return 0
    r = min(r, n - r)
    if r == 0: return 1
    if r == 1: return n
    numerator = list(range(n-r+1, n+1))
    denominator = list(range(1, r+1))
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result

def solve(n, k):
    if k == 0:
        return 1

    p = int(str(n)[0])
    l = len(str(n))
    if l < k:
        return 0
    res = 0
    for r in range(k-1, l-1):
        res += comb(r, k-1) * 9 ** (k - 1) * 9
    res += comb(l-1, k-1) * 9 ** (k - 1) * (p - 1)
    if k == 1:
        res += 1
    else:
        res += solve(int(str(n)[1:]), k-1)
    return res

n, k = map(int, sys.stdin.read().split())
def main():
    return solve(n, k)

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
k=int(input())
keta=len(str(n))
sn=str(n)
dp=[[[0]*(k+1) for j in range(keta)] for i in range(2)]

for i in range(keta):
    if i==0:
        dp[0][0][0]=1
        dp[0][0][1]=int(sn[i])-1
        dp[1][0][1]=1
    else:
        for j in range(k+1):
            if j!=k:
                dp[0][i][j]+=dp[0][i-1][j]
                dp[0][i][j+1]+=dp[0][i-1][j]*9
                if int(sn[i])==0:
                    dp[1][i][j]+=dp[1][i-1][j]
                else:
                    dp[1][i][j+1]+=dp[1][i-1][j]
                    dp[0][i][j]+=dp[1][i-1][j]
                    dp[0][i][j+1]+=dp[1][i-1][j]*(int(sn[i])-1)
            else:
                dp[0][i][j]+=dp[0][i-1][j]
                if int(sn[i])==0:
                    dp[1][i][j]+=dp[1][i-1][j]
                else:
                    dp[0][i][j]+=dp[1][i-1][j]

print(dp[0][-1][-1]+dp[1][-1][-1])

Submission status: Accepted

Solution code:
n = str(input())
k = int(input())
m = len(n)
dp = [[[0,0] for __ in range(k+2)] for _ in range(m+1)]
dp[0][0][0] = 1
for i in range(m):
    d = int(n[i])
    for j in range(k+1):
        for s in range(2):
            for c in range(10):
                if (not s ) and c>d:
                    continue
                dp[i+1][j+(c!=0)][s or (c<d)] += dp[i][j][s]
print(dp[m][k][0]+dp[m][k][1])

Submission status: Accepted

Solution code:
digits = [int(c) for c in input()]
n = len(digits)
m = int(input())

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

for i, digit in enumerate(digits):
    for j in range(m + 1):
        for k in range(2):
            for d in range(10 if k else digit + 1):
                if j + (d > 0) <= m:
                    dp[i + 1][j + (d > 0)][k or (d < digit)] += dp[i][j][k]

print(sum(dp[n][m]))

Submission status: Accepted

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

l = len(S)

dp0 = [[0 for j in range(K + 1)] for i in range(l + 1)] #　以下未確定
dp1 = [[0 for j in range(K + 1)] for i in range(l + 1)] # 以下確定

dp0[0][0] = 1
for i in range(l):
    n = int(S[i])
    for j in range(K + 1):
        for d in range(10):
            nk = j
            if j > K: # j == Kの場合は残りがすべて0なら配れるので
                continue

            if d > 0:
                nk += 1
                if nk > K:
                    continue
            # 確定済みdp1の配り
            dp1[i + 1][nk] += dp1[i][j]

            #　非確定dp0の配り
            if d > n:
                continue
            elif d == n:
                dp0[i + 1][nk] += dp0[i][j]
            elif d < n:
                dp1[i + 1][nk] += dp0[i][j]

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

Submission status: Accepted

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

from functools import lru_cache

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

@lru_cache(None)
def F(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
    assert N >= 0
    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:
        # 1の位が nonzero
        ret += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    # 1の位が zero
    ret += F(q, K)
    return ret

# F(100, 1), F(25, 2), F(314159, 2)

print(F(N, K))

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(10 ** 7)

# 桁DP
# 再帰

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


# 組み合わせの数
def comb(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n-k))


# i桁目から
# 残りk個 Non-Zero
# Nよりもsmallerか？
# というときの組み合わせの数
def CntAlmostZero(i, k, smaller):
    # N桁まで取り出した時
    if i == lenN:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    # Nよりも小さい時
    if smaller:
        # 残りの桁でK個使える時
        if (lenN - i) >= k:
            return comb(lenN - i, k) * (9 ** k)
        # 無理なら 0
        else:
            return 0
    # 前がNと同じ桁の時(初期は0なので必ずこっち)
    else:
        # 見てる桁が0の時
        if N[i] == '0':
            return CntAlmostZero(i + 1, k, False)
        # 見てる桁が0以外の時
        else:
            # 0だったら
            zero = CntAlmostZero(i+1, k, True)
            # 同じだったら
            same = CntAlmostZero(i+1, k-1, False)
            # その間だったら
            aida = CntAlmostZero(i+1, k-1, True) * (int(N[i]) - 1)

            return zero + same + aida

    return 1


ans = CntAlmostZero(0, K, False)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=input()
K=int(input())
#Nは最大で100桁あるので、整数では扱いにくい
#そこでstringで入力する

#桁DPの典型的な問題
#まず、Nの具体的な値は無視して、以下のDPをする
#dp[i][j][k]=[j*10^i,(j+1)*10^i)までに0でない桁がk桁あるような数の個数
#このDPは、以下の遷移で求まる
#dp[i][j][k]=(i=0 j=0 k=0)1
#            (i=0 j=0 k!=0)0
#            (i=0 j!=0 k=1)1
#            (i=0 j!=0 k!=1)0
#            (i!=0 j=0)Σ[j,0~9] dp[i-1][j][k]
#            (i!=0 j!=0)Σ[j,0~9] dp[i-1][j][k-1]

dp = [[[0 for i in range(5)] for j in range(11)] for k in range(104)]
for j in range(10):
    if j==0:
        dp[0][j][0]=1
    else:
        dp[0][j][1]=1

for k in range(K+1):
    for i in range(len(N)):
        if i==0:
            continue
        for j in range(10):
            if j==0:
                for l in range(10):
                    dp[i][j][k]+=dp[i-1][l][k]
            elif (k != 0):
                for l in range(10):
                    dp[i][j][k]+=dp[i-1][l][k-1]


#そうしてDPのボードが完成したら答えを求める
#Nの上からi桁目をDとおき、[0,D)だけdp[i][j][k]を足す
#なお、最後の桁だけは[0,D]
#Dが0のときは以降の桁に0が残り続けるので、kをデクリメントする
#全ての桁を調べるかkが負になったら終了

Ans=0
k=K
for i in range(len(N)):
    D=int(N[i])
    if i==len(N)-1:
        D+=1
    for j in range(D):
        Ans+=dp[len(N)-i-1][j][k]
    if D!=0:
        k-=1
    if k<0:
        break

print(Ans)