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 = str(input())
k = int(input())

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

for i in range(len(n)):
    now = int(n[i])
    for j in range(2):
        for non_zero in range(k+1):
            for m in range(10):
                if j == 1 or (j == 0 and m < now):
                    next_j = 1
                elif m == now:
                    next_j = 0
                else:
                    continue

                if non_zero == k and m != 0:
                    continue
                elif m == 0:
                    next_non_zero = non_zero
                else:
                    next_non_zero = non_zero + 1
                
                DP[i+1][next_j][next_non_zero] += DP[i][j][non_zero]

ans = DP[len(n)][1][k] + DP[len(n)][0][k]
print(ans)
# print(DP)

Submission status: Accepted

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

l = len(N)

nozero = [0]*l
if N[0] != "0":
    nozero[0] = 1

for i in range(1, l):
    nozero[i] = nozero[i-1]
    if N[i] != "0":
        nozero[i] += 1 

dp0 = [[0]*2 for _ in range(l)]
dp1 = [[0]*2 for _ in range(l)]
dp2 = [[0]*2 for _ in range(l)]
dp3 = [[0]*2 for _ in range(l)]

for i in range(l):
    dp0[i][0] = 1

def dp(K):
    dps = [dp0, dp1, dp2, dp3]
    return dps[K]

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

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

            
        if nozero[i] == k:
            dp(k)[i+1][1] += (sum(dp(k)[i])-1)*1
        else:
            dp(k)[i+1][1] += sum(dp(k)[i])*1

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

Submission status: Accepted

Solution code:
N=str(input())
K=int(input())
length=len(N)
dp=[[0]*10 for _ in range(length+1)]
dp[0][0]=1
def index(flag_less,k):
  if flag_less==0 and k==0:
    return 0
  elif flag_less==1 and k==0:
    return 1
  elif flag_less==0 and k==1:
    return 2
  elif flag_less==1 and k==1:
    return 3
  elif flag_less==0 and k==2:
    return 4
  elif flag_less==1 and k==2:
    return 5
  elif flag_less==0 and k==3:
    return 6
  elif flag_less==1 and k==3:
    return 7
  elif flag_less==0 and k==4:
    return 8
  else:
    return 9
  
for i in range(length):
  max_digit=int(N[i])
  for state in range(10):
    range_digit=9 if state%2 else max_digit
    for d in range(range_digit+1):          # 注意
      flag_less_next=0
      if state%2==1 or d<max_digit:
        flag_less_next=1
      prev_k=state//2
      if d!=0:
        next_k=min(4,prev_k+1)      
      else:
        next_k=prev_k
      next_state=index(flag_less_next,next_k)  # flag_less_next+2*next_kでもいい
      dp[i+1][next_state]+=dp[i][state]

print(dp[length][2*K]+dp[length][2*K+1])

Submission status: Accepted

Solution code:
import math
N = int(input())
K = int(input())
# keta → 10 なら 2
S = str(N)
keta = len(S)


dp1 = [ [ 0 ]* (keta + 1)  for _ in range(100) ] #超えないことが確定した方
dp2 = [  [ 0 ]* (keta + 1)  for _ in range(100) ] # 超える可能性がある方
# dp[以下確定済みフラグ][0でないの個数 k ][上からn桁目か] の条件を満たしたものの個数

i = int(S[0])
dp2[0][0] = 1 #超える可能性はある

for n in  range(0,keta):
    # for i in range(0,10): #次の桁に来る候補  #ここを省略して 1～9 と 0で場合分け
    for k in range(0, K + 1):
        num = int(S[n])  #実際の数字
        num_to_9  = 9 - num  # 5 だったら 6,7,8,9
        num_hiku1_to_1 = max(0,num - 1) #未満が確定する 0 以外の数
        # 確定から確定
        #確定済みには何をつけても良い

        if num == 0:
            dp1[k + 1][n + 1] += dp1[k][n] * 9 # 1~ 9
            dp1[k][n + 1] += dp1[k][n] # 0を足して確定
            # dp1[k][n + 1] += dp2[k][n]
            dp2[k][n + 1] += dp2[k][n] #0を足して未定パターン

        else:
            dp1[k + 1][n + 1] += dp1[k][n] * 9 # 1~ 9 を 超えないことが確定したやつに足したパターン
            dp1[k + 1][n + 1] += dp2[k][n] * (num - 1)  # 超えないやつを未定に足したパターン
            dp2[k + 1][n + 1] += dp2[k][n] #未定に引き続き未定になるやつを足したパターン

            # 0 を足すパターンがまだ
            dp1[k][n + 1] += dp1[k][n] # 超えないが確定したやつに0を足すパターン
            #  当然dp1に遷移

            dp1[k][n + 1] += dp2[k][n] # 超えるかもなやつに0を足すパターン
            # num > 0なのでdp2 からdp1に遷移
        # 未確定から未確定


print(dp1[K][keta] + dp2[K][keta])

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

s = input()
k = ii()

#dp[keta][not0nokosuu]
n = len(s)
dp = [[0]*(n) for _ in range(4)]
dp[0][0] = 1
for i in range(1,n):
    #のこり0のやつ
    dp[0][i] = dp[0][i-1] 
    #のこり1のやつ
    dp[1][i] = dp[0][i-1] * 9 + dp[1][i-1]
    #のこり2のやつ
    dp[2][i] = dp[1][i-1]*9 + dp[2][i-1]
    dp[3][i] = dp[2][i-1]*9 + dp[3][i-1]

ans = 0
for i in range(n):
    ima = int(s[i])
    if i ==-1 :
        ans += (ima -1) * dp[k-1][n-1-i]
        k -= 1
    else:
        if ima != 0:
            ans += (ima -1) * dp[k-1][n-1-i] + dp[k][n-1-i]
            k -= 1
    if k == 0:
        ans += 1
        break
print(ans)

Submission status: Accepted

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

if len(n) <= k:
    cnt = 0
    for i in range(1,int(n)+1):
        if len(str(i)) - str(i).count('0') == k:
            cnt += 1
    print(cnt)
    exit()

cnt = 0
l = len(n)
def combi(n,k):
    ans = 1
    if k == 0:
        return ans
    for i in range(k):
        ans = ans * (n-i) // (i+1)
    return ans
flag = 0
for i in range(l):
    if flag > k:
        break
    if n[i] == '0':
        if i == l-1 and k == flag:
            cnt += 1
        continue
    flag += 1
    cnt += int(((int(n[i])-1)*9**(k-flag))*combi(l-i-1,k-flag) + 9**(k-flag+1)*combi(l-i-1,k-flag+1))

print(cnt)

Submission status: Accepted

Solution code:
def main():
    s = [int(char) for char in input()]
    l = len(s)
    k = int(input())

    tmp = 0
    nonzero = []
    for number in s:
        if number > 0:
            tmp += 1
        nonzero.append(tmp)
    nonzero.append(0)  # let nonzero[-1] be 0

    def binomial(n, k):
        if n < k or n < 0 or k < 0:
            return 0
        if k == 0:
            return 1
        if k == 1:
            return n
        if k == 2:
            return n * (n-1) // 2
        if k == 3:
            return n * (n-1) * (n-2) // 6
        raise ValueError

    def dp(i, _cache={-1: 0}):
        if i in _cache:
            return _cache[i]
        if nonzero[i-1] > k or s[i] == 0:
            result = dp(i-1)
            _cache[i] = result
            return result
        if nonzero[i-1] == k:
            result = dp(i-1) + 1
            _cache[i] = result
            return result
        result = (
            dp(i-1) +
            (s[i] - 1) * binomial(l - 1 - i, k - nonzero[i-1] - 1) *
            9 ** (k - nonzero[i-1] - 1) +
            binomial(l - 1 - i, k - nonzero[i-1]) *
            9 ** (k - nonzero[i-1])
        )
        _cache[i] = result
        return result
    
    print(dp(l-1) + (nonzero[l-1] == k))


main()

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)
n = int(input())
k = int(input())


@lru_cache(maxsize=None)
def f(n, k):
    if k == 0:
        return 1
    if len(str(n)) == 1:
        if k >= 2:
            return 0
        if k == 1:
            return n

    r = n % 10
    m = (n - r) // 10
    return r * f(m, k-1) + (9 - r) * f(m-1, k-1) + f(m, k)


print(f(n, k))

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  l=len(s)
  _k=I()

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

  for i in range(l):
    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:
            nj+=1

          if nj>_k:
            continue

          if k==0:
            if nd>d:
              nk=1
            if nd<d:
              continue

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

  return dp[l][_k][0]+dp[l][_k][1]

# main()
print(main())

Submission status: Accepted

Solution code:
#これはmaspyさんの提出コードの写経です
from sys import setrecursionlimit
setrecursionlimit(10**6) 

from sys import stdin
from functools import lru_cache
n = int(stdin.readline().rstrip())
k = int(stdin.readline().rstrip())
#n以下の数字で0でないものがちょうどk個
@lru_cache(maxsize=None)
def kosuu(n,k):
    #残り10以下の場合
    if n < 10:
        if k == 0:
            return 1
        if k == 1:
            return n
        return 0
    q = n//10#商
    r = n%10#余り
    ret = 0
    if k >= 1:
        # 1の位が nonzero
        ret += kosuu(q, k-1) * r
        ret += kosuu(q-1, k-1) * (9-r)
    ret += kosuu(q,k)
    return ret
print(kosuu(n,k))

Submission status: Accepted

Solution code:
from math import factorial as f
from functools import reduce
def C(n,k):
    a,b=sorted((k,n-k))
    return reduce(int.__mul__, range(b+1,n+1),1) // f(a)

def almost_everywhere_zero(v, k):
    if not v or not k: return 0
    s = str(v)
    n,d = len(s), int(s[0])
    
    if k>n: return 0
    
    below = 9**k * C(n-1,k) if n>k else 0
    return below + ( d if k==1 else (d-1) * 9**(k-1) * C(n-1,k-1) + almost_everywhere_zero(int(s[1:]), k-1) )
N = input()
K = int(input())
print(almost_everywhere_zero(N,K))

Submission status: Accepted

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

l = len(S)

MOD = 1000000007

# [桁数][未満][0でない数の合計数]
dp = [[[0] * (l + 1) for _ in range(2)] for _ in range(l + 1)]


# 初期化
dp[0][False][0] = 1

for i in range(l):
    cur = int(S[i])

    for j in range(i + 1):
        # true -> true
        for k in range(10):
            if k == 0:
                dp[i + 1][True][j] += dp[i][True][j]
            else:
                dp[i + 1][True][j + 1] += dp[i][True][j]

        # false -> true
        for k in range(cur):
            if k == 0:
                dp[i + 1][True][j] += dp[i][False][j]
            else:
                dp[i + 1][True][j + 1] += dp[i][False][j]

        # false -> false
        if cur == 0:
            dp[i + 1][False][j] += dp[i][False][j]
        else:
            dp[i + 1][False][j + 1] += dp[i][False][j]

if K > l:
    print(0)
else:
    print(dp[l][True][K] + dp[l][False][K])

Submission status: Accepted

Solution code:
n=int(input())
k=int(input())
l=[int(i) for i in "0"+str(n)]
# [0]=n [1]<n
dp=[[[0]*5,[0]*5] for i in "ww"]
dp[0][0][0]=1
for i,j in enumerate(str(n),start=1):
    for p in range(k+1):
        if dp[i%2-1][0][p]:
            dp[i%2][0][p+[0,1][l[i]>0]]=1
            for q in range(l[i]):
                dp[i%2][1][p+[0,1][q>0]]+=1
        if dp[i%2-1][1][p]:
            dp[i%2][1][p]+=dp[i%2-1][1][p]
            dp[i%2][1][p+1]+=dp[i%2-1][1][p]*9
    for p in range(10): dp[i%2-1][p//5][p%5]=0
print(dp[0][0][k]+dp[1][0][k]+dp[0][1][k]+dp[1][1][k])

Submission status: Accepted

Solution code:
n=int(input())
k=int(input())
l=[int(i) for i in "0"+str(n)]
# [0]=n [1]<n
dp=[[[0]*5,[0]*5] for i in "ww"]
dp[0][0][0]=1
for i,j in enumerate(str(n)):
    i+=1
    for p in range(k+1):
        if dp[i%2-1][0][p]:
            dp[i%2][0][p+[0,1][l[i]>0]]=1
            for q in range(l[i]):
                dp[i%2][1][p+[0,1][q>0]]+=1
        if dp[i%2-1][1][p]:
            dp[i%2][1][p]+=dp[i%2-1][1][p]
            dp[i%2][1][p+1]+=dp[i%2-1][1][p]*9
    for p in range(10): dp[i%2-1][p//5][p%5]=0
print(dp[0][0][k]+dp[1][0][k]+dp[0][1][k]+dp[1][1][k])

Submission status: Accepted

Solution code:
n=int(input())
k=int(input())
l=[int(i) for i in "0"+str(n)]
# [0]=n [1]<n
dp=[[[0]*5,[0]*5] for i in "ww"]
dp[0][0][0]=1
v=0
for i,j in enumerate(str(n)):
    i+=1
    v=v*10+l[i]
    for p in range(k+1):
        if dp[i%2-1][0][p]:
            dp[i%2][0][p+[0,1][l[i]>0]]=1
            for q in range(l[i]):
                dp[i%2][1][p+[0,1][q>0]]+=1
        if dp[i%2-1][1][p]:
                dp[i%2][1][p]+=dp[i%2-1][1][p]
                dp[i%2][1][p+1]+=dp[i%2-1][1][p]*9
    for p in range(10): dp[i%2-1][p//5][p%5]=0
print(dp[0][0][k]+dp[1][0][k]+dp[0][1][k]+dp[1][1][k])

Submission status: Accepted

Solution code:
n = input()
k = len(n) - int(input())
if k < 0:
    print(0)
    exit()

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

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

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

Submission status: Accepted

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

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

n = len(N)
for i in range(n):
    nd = int(N[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:
                    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:
from scipy.misc import comb
def solve(i,k,smaller):
    if i == len(S):
        if k == 0:
            #0以外の個数がkと等しいので答えとしてカウントできる
            return 1
        else:
            #0以外の個数がkと等しくないので答えとしてカウント不可
            return 0 
    
    if k ==0:
        #kの個数を使い切りこれ以上下の桁は0で埋まり1通りの為
        return 1
    
    if smaller :
        return comb(len(S)-i,k)*pow(9,k)
    else:
        if S[i] =="0":
            return solve(i+1,k,False)
        else:
            zero = solve(i+1,k,True)
            aida = solve(i+1,k-1,True)*(int(S[i])-1)
            ici  = solve(i+1,k-1,False)
            
            return zero+aida+ici
            
N = int(input())
S = str(N)
K = int(input())

ans = round(solve(0,K,False))

print(int(ans))

Submission status: Accepted

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

dp0 = [[0] * (k + 1) for _ in range(l + 1)]
dp1 = [[0] * (k + 1) for _ in range(l + 1)]

for i in range(1, l + 1):
    dp0[i][0] = 1

dp1[0][0] = 1

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

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

Submission status: Accepted

Solution code:
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]
dp=[[[0]*5,[0]*5] for i in range(x)]
dp[0][0][0]=1
r=0
#dp 0=n, 1=under
for i in range(1,x):
    for j in range(2):
        dp[i][1][0]=1
        for p in range(1,k+1):
            if j==0 and l[i]==0:
                dp[i][0][p]=dp[i-1][0][p]
            elif j==0 and l[i]!=0 and dp[i-1][0][p-1]:
                dp[i][0][p]=1
            if j==1:
                dp[i][1][p]=dp[i-1][1][p]+(dp[i-1][1][p-1]*9)+(dp[i][0][p]*max(0,l[i]-1))+([0,1][l[i]!=0 and dp[i-1][0][p]])
print(dp[-1][0][k]+dp[-1][1][k])

Submission status: Accepted

Solution code:
n_str = input()  # 3***
k = int(input())

dp1 = [[0] * (k + 2) for _ in range(len(n_str) + 1)]
dp2 = [[0] * (k + 2) for _ in range(len(n_str) + 1)]
# dp1[i][j] : 上から i 桁はnと一致していて、0でない数が j 個現れているような数
# dp2[i][j] : 上から i 桁が既にnより小さく、0でない数が j 個現れているような数

dp1[0][0] = 1
# dp2[0][1] = int(n_str[0]) - 1
# dp2[0][0] = 1

for i in range(len(n_str)):
    for j in range(k + 1):
        if n_str[i] != '0':
            dp1[i + 1][j + 1] += dp1[i][j]

            dp2[i + 1][j + 1] += dp1[i][j] * (int(n_str[i]) - 1)
            dp2[i + 1][j + 1] += dp2[i][j] * 9

            dp2[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        else:
            dp1[i + 1][j] += dp1[i][j]

            dp2[i + 1][j + 1] += dp2[i][j] * 9
            dp2[i + 1][j] += dp2[i][j]

# print(*dp1, sep='\n')
# print(*dp2, sep='\n')
ans = dp1[len(n_str)][k] + dp2[len(n_str)][k]
print(ans)

Submission status: Accepted

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

X = str(N)

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

for i in range(len(X)):
    digit = int(X[i])
    for j in range(2):
        for k in range(K+1):
            for d in range(10 if j == 1 else digit+1):
                if k + int(d != 0) <= K:
                    dp[i+1][j | (d < digit)][k + (d!=0)] += dp[i][j][k]
print(dp[-1][0][-1]+dp[-1][1][-1])

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())
n=[int(i) for i in str(N)]
K=int(input())
L=len(n)
dp=np.zeros((L+1,K+1,2),dtype=int)
dp[0,0,0]=1

for i in range(L):
  for j in range(K+1):
    for smaller in range(2):
      m=10 if smaller else n[i]+1
      for x in range(m):
        if int(j+(x!=0))>K:
          continue
        #i桁目がxだったときにdp[i][smaller][j]をどこに足しますか？
        dp[i+1,j+(x!=0),smaller or x<n[i]]+=dp[i,j,smaller]
        #print(i+1,j+(x!=0),int(smaller or x<n[i]),i,j,smaller)
        
print(dp[L,K].sum())

Submission status: Accepted

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


dp0 = [[0]*5 for i in range(len(n)+1)]
dp1 = [[0]*5 for i in range(len(n)+1)]

dp0[0][0] = 1


for i in range(1, len(n)+1):
    nn = int(n[i-1])
    for j in range(4):
        dp0[i][j] += dp0[i-1][j]*(nn==0)
        dp1[i][j] += dp1[i-1][j] + dp0[i-1][j]*(nn!=0)
        dp0[i][j+1] += dp0[i-1][j]*(nn!=0)
        dp1[i][j+1] += dp1[i-1][j]*9 + dp0[i-1][j]*(nn-1)*(nn!=0)

print(dp0[len(n)][k]+dp1[len(n)][k])

Submission status: Accepted

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

#桁DP
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:
N = int(input())
K = int(input())

#桁DP
#dp0[i]: i桁目まで見てN未満が確定, dp1: 未確定
string = str(N)
digits = len(string)

#dp*[i][j]=i桁目まで見て0でない数字がK個あるようなものの個数
dp0 = [[0] * (K+1) for _ in range(digits+1)]
dp1 = [[0] * (K+1) for _ in range(digits+1)]

dp1[0][0] = 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):
                nj = j + (1 if nd != 0 else 0)
                if nj > K: continue
                nk = k
                if k == 1:
                    if nd < d: nk = 0
                    elif nd > d: continue
                dp_b = dp0 if k == 0 else dp1
                dp_a = dp0 if nk == 0 else dp1
                dp_a[ni][nj] += dp_b[i][j]

print(dp0[digits][K] + dp1[digits][K])

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Mon Mar  2 04:27:45 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

s = ns()
N = len(s)
K = ni()
dp = [[[0] * 4 for _ in range(2)] for _ in range(N + 1)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(2):
        D = int(s[i])
        n = 9 if j == 1 else D
        for d in range(n + 1):
            for k in range(4):
                ni, nj, nk = i + 1, j, k
                if d != 0:
                    nk += 1
                if nk > K:
                    continue
                if d < D:
                    nj = 1
                dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

Solution code:
N = input()
digits = len(N)
K = int(input())
dp0 = [[0]*5 for i in range(digits + 1)] 
dp1 = [[0]*5 for i in range(digits + 1)]
dp0[0][0] = 1
for i, n in enumerate(N):
    n = int(n)
    for j in range(4):
        if n == 0:
            dp0[i+1][j] += dp0[i][j]
            dp1[i+1][j] += dp1[i][j]
            dp1[i+1][j+1] += 9 * dp1[i][j]
        else:
            dp0[i+1][j+1] += dp0[i][j]
            dp1[i+1][j] += dp0[i][j] + dp1[i][j]
            dp1[i+1][j+1] += (n - 1) * dp0[i][j] + 9 * dp1[i][j]
print(dp0[digits][K] + dp1[digits][K])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

# m digits, k, less than flag
n = input()
K = int(input())


def func(i, k, free=False):
    # rest digits
    m = len(n) - i

    # cannot fill m digits with 0 * k
    if k > m:
        return 0

    if m == 0:
        return 1
    # fill all digits with 0
    if k == 0:
        return 1

    if free:
        a = 9 ** k
        # print(a)
        for j in range(k):
            a *= (m - j)
        for j in range(k):
            a = a // (j + 1)
        # print(a)
        return a

    else:
        if n[i] != '0':
            # fill with 0
            a = func(i + 1, k, free=True)

            # 1, 2, ..., n[i] - 1
            b = (int(n[i]) - 1) * func(i + 1, k - 1, free=True)

            # n[i]
            c = func(i + 1, k - 1, free=False) 
            # print(i, a, b, c, k, m)
            return a + b + c
        else:
            # fill with 0
            c = func(i + 1, k, free=False)
            return c


print(func(0, K, free=False))

Submission status: Accepted

Solution code:
import functools

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

@functools.lru_cache(maxsize=2048)
def nCk(n, k):
    if k == 0:
        return 0
    elif k == 1:
        return n
    elif k == 2:
        return (n * (n-1)) // 2
    return (n * (n-1) * (n-2)) // 6

def slowsolve(N, K):
    if not N:
        return 0, {}
    ans = 0
    meta = {}
    for i in range(1, int(N) + 1):
        if len(str(i)) - str(i).count("0") == K:
            meta.setdefault(len(str(i)), 0)
            meta[len(str(i))] += 1
            ans += 1
    return ans, meta

def clean(N):
    clean_N = []
    for n in N:
        if n == "0" and not clean_N:
            pass
        else:
            clean_N.append(n)
    if clean_N:
        return "".join(clean_N)
    return ""

@functools.lru_cache(maxsize=2048)
def solve(N, K):
    N = clean(N)

    if len(N) <= 3:
        return slowsolve(N, K)[0]
    elif K == 0:
        return 0
    else:
        m = int(N[0])

        # 一番上を0にする
        ans = solve("9" * len(N[1:]), K)

        if K == 3:
            # 一番上を1 ~ m - 1にする
            # => 下の部分から2か所選び、それぞれ1 ~ 9
            ans += (m - 1) * nCk(len(N[1:]), 2) * 9 * 9
            # 一番上をmにする
            ans += solve(N[1:], K - 1)
        elif K == 2:
            # 一番上を1 ~ m - 1にする
            # => 下の部分から1か所選び、1 ~ 9
            ans += (m - 1) * len(N[1:]) * 9
            # 一番上をmにする
            ans += solve(N[1:], K - 1)
        elif K == 1:
            # 一番上をmにする
            ans += m
        return ans


print(solve(N, K))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

result = 0
for i in range(101):
    if n < 10 ** i:
        if i < k:
            break
        if i > k:
            result += cmb(i-1, k) * 9**k
        s = str(n)
        result += (int(s[0])-1) * cmb(i-1, k-1) * (9 **(k-1))
        if k > 1:
            ind = -1
            for j in range(1, i):
                if s[j] != '0':
                    ind = j
                    break
            if ind == -1:
                break
            if i - ind >= k:
                result += cmb(i-ind-1, k-1) * (9**(k-1))
            result += (int(s[ind])-1) * cmb(i-ind-1, k-2) * (9**(k-2))
            if k > 2:
                ind2 = -1
                for j in range(ind+1, i):
                    if s[j] != '0':
                        ind2 = j
                        break
                if ind2 == -1:
                    break
                result += (i-ind2-1) * 9 + int(s[ind2])
            else:
                result+=1
        else:
            result+=1
        break
print(result)

Submission status: Accepted

Solution code:

import numpy as np

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

dp = np.zeros((len(N), 2, K+1), dtype=np.int)

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

#for k in range(K+1) :
#    print( "_" * 10 )
#    print( "K == {}".format(k) )
print( dp[len(N)-1][0][K] + dp[len(N)-1][1][K] )

Submission status: Accepted

Solution code:
s = list(input())
n = len(s)
k = int(input())
#dp1[i][j] := i桁目まで確定させ、j個0でないものを使った後に、nより小さいことが確定している
#dp2[i][j] := i桁目まで確定させ、j個0出ないものを使った後に、nより小さいことが確定していない
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
dp1[0][1] = int(s[0]) - 1
dp2[0][1] = 1
for i in range(1,n):
    dp1[i][0] = 1
    for j in range(1,k+1):
        x = int(s[i])
        if x != 0:
            #今回の数字を使うと、確定していないものは確定しない
            dp2[i][j] += dp2[i-1][j-1]
            dp1[i][j] += dp1[i-1][j-1] * 9 + dp2[i-1][j-1] * (x-1)
            dp1[i][j] += dp1[i-1][j] + dp2[i-1][j]
        else:
            dp1[i][j] += dp1[i-1][j-1] * 9 + dp1[i-1][j]
            dp2[i][j] += dp2[i-1][j]
print(dp1[n-1][k] + dp2[n-1][k])

Submission status: Accepted

Solution code:
from decimal import*
from fractions import*
import math
import functools

s=input()
k=input()
k=(int)(k)

n=len(s)
dp=[[[0 for mind in range (2)] for j in range(k+5)] for i in range(n+5)]

dp[0][0][0]=1
for i in range(n):
    for j in range(2):
        for cnt in range(k+1):
            pre_num=1
            if(j!=0):
                pre_num=9
            else:
                pre_num=(int)(s[i])
            for digit in range(pre_num+1):
                cur=j
                if(digit<pre_num): 
                    cur=1
                dp[i+1][cnt+(digit!=0)][cur]+=dp[i][cnt][j]
sum=dp[n][k][0]+dp[n][k][1]
print(sum)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    N = input().strip()
    M = len(N)
    K = int(input())

    dp1 = [[0 for _ in range(K + 1)] for __ in range(M)]
    dp2 = [[0 for _ in range(K + 1)] for __ in range(M)]

    dp1[0][0] = 1
    dp1[0][1] = int(N[0]) - 1
    dp2[0][1] = 1

    for i in range(1, M):
        a = int(N[i])
        for k in range(K + 1):
            dp1[i][k] += dp1[i - 1][k]
            if a > 0:
                dp1[i][k] += dp2[i - 1][k]
            
            if a == 0:
                dp2[i][k] = dp2[i - 1][k]
            else:
                if k > 1:
                    dp2[i][k] = dp2[i - 1][k - 1]

        for k in range(1, K + 1):
            dp1[i][k] += 9 * dp1[i - 1][k - 1]
            if a > 0:
                dp1[i][k] += (a - 1) * dp2[i - 1][k - 1]

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 桁DPは、
# 「０以上N以下の整数で、ある条件を満たすものの個数を求めよ」
# 「０以上N以下の整数で、ある条件を満たすものの最大値を求めよ」
# といった問題を解く場合に用いられる方法です。
# https://qiita.com/pinokions009/items/1e98252718eeeeb5c9ab

n = input()
k_in = int(input())

# dp[i][smaller][k] := 上位からi桁目まで見て、smaller（nと一致しているいない）で非0の桁がk個だけあるものの数
# i <= 101, k <= 3 より、マス目の数は高々606。

# k = 4まで取っておくと（番兵）漸化式の場合分けをしなくて良いから楽。ただしループは
dp = [[[0 for _ in range(4 + 1)] for _ in range(2)] for _ in range(len(n))] 

digit = int(n[0])

dp[0][False][0] = 1
dp[0][False][1] = digit - 1
dp[0][True][1] = 1

for i in range(len(n) - 1):
    for smaller in [True, False]:
        for k in range(4):
            # 配るDPのほうが楽そうな予感
            if not smaller:
                # 0をつけたら
                dp[i+1][False][k] += dp[i][smaller][k]
                # 1~9をつけたら
                dp[i+1][False][k+1] += 9 * dp[i][smaller][k]
            else:
                next_digit = int(n[i+1])
                if next_digit == 0:
                    # 0をつけるしかない
                    dp[i+1][True][k] += dp[i][smaller][k]
                else:
                    # 0をつけたら
                    dp[i+1][False][k] += dp[i][smaller][k]
                    # 1〜(next_digit - 1)をつけたら
                    dp[i+1][False][k+1] += (next_digit - 1) * dp[i][smaller][k]
                    # next_digit をつけたら
                    dp[i+1][True][k+1] += dp[i][smaller][k]

print(dp[len(n)-1][True][k_in] + dp[len(n)-1][False][k_in])