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())
S = str(N)
m = len(S)
K = int(input())

#dp[i][j][k]: 上からi桁目までに0以外がj個あって、Nと一致しているならばk=0
dp = [[[0] * 2 for _ in range(4)] for _ in range(m+1)]
dp[0][0][0] = 1

for i in range(m): #i=0は架空の桁に相当。
  for j in range(4):
    for k in range(2):
      #dp[i][j][k]という状態が次の桁でどこに遷移するかを考える。遷移先のni,nj,nkを決定する。
      nd = int(S[i]) #Nのi桁目。1桁目はS[0]。
      for d in range(10): #dというのが今の桁(i+1)の値
        ni = i+1 #今の桁
        nj = j
        nk = k
        if d != 0: #もし今の桁が0でなければjは一つ増える。
          nj += 1
        if nj > K: #もしnjが許容値のKを超えたら無視。
          continue
        if k == 0: #ここまで完全一致の時
          if d > nd: #今の桁がNのi桁目より大きいつまりNを超えているので無視。
            continue
          elif d < nd: #今の桁がNのi桁目より小さいなら完全一致ではないのでnk=1と変更。
            nk = 1
        dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()
n = int(s)
keta = len(s)
k = int(input())
# k=1,2,3
ans = 0

dp = [[[0] * (2) for _ in range(k + 1)] for _ in range(keta + 1)]
dp[0][0][0] = 1
for i in range(keta):
    d = int(s[i])
    for j in range(k + 1):
        for smaller in range(2):

            for t in range(10):
                ni = i + 1
                nj = j
                nsmaller = smaller
                if t > 0:
                    nj = j + 1
                if nj > k:
                    continue
                if nsmaller == 0:
                    if t > d:
                        continue
                    if t < d:
                        nsmaller = 1
                dp[ni][nj][nsmaller] += dp[i][j][smaller]
print(dp[keta][k][1] + dp[keta][k][0])

Submission status: Accepted

Solution code:

nn = list(map(int, list(input())))
L = len(nn)
K = int(input())

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


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


for i, n in enumerate(nn):
    for x in range(0, 10):
        if x == 0:
            dp[i + 1][1][0] += dp[i][1][0]
            dp[i + 1][1][1] += dp[i][1][1]
            dp[i + 1][1][2] += dp[i][1][2]
            dp[i + 1][1][3] += dp[i][1][3]
        else:
            dp[i + 1][1][1] += dp[i][1][0]
            dp[i + 1][1][2] += dp[i][1][1]
            dp[i + 1][1][3] += dp[i][1][2]

    for x in range(0, n + 1):
        if x == 0:
            dp[i + 1][0 if x == n else 1][0] += dp[i][0][0]
            dp[i + 1][0 if x == n else 1][1] += dp[i][0][1]
            dp[i + 1][0 if x == n else 1][2] += dp[i][0][2]
            dp[i + 1][0 if x == n else 1][3] += dp[i][0][3]
        else:
            dp[i + 1][0 if x == n else 1][1] += dp[i][0][0]
            dp[i + 1][0 if x == n else 1][2] += dp[i][0][1]
            dp[i + 1][0 if x == n else 1][3] += dp[i][0][2]


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

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

dp1 = [[0] * (K + 1) for _ in range(n + 1)] #N以下が確定していて、0以外の数をk個使ったとき
dp2 = [0] * (n + 1) #N以下が確定していないときの0以外の数の個数

for i in range(n):
    a = int(N[i])

    if a != 0:
        dp2[i + 1] = dp2[i] + 1
    else:
        dp2[i + 1] = dp2[i]
    
    #0を使うことで0以外の数が増えないパターン
    for k in range(K + 1):
        dp1[i + 1][k] = dp1[i][k]

    #0以外の数を使うことで0以外の数が増えるパターン
    for k in range(K):
        dp1[i + 1][k + 1] += dp1[i][k] * 9
    
    #今回でN以下が確定するパターン
    tmp = dp2[i] #確定する前までに0以外の数を何個使っているか
    if a == 0: #今回でN以下が確定することはない
        continue
    else:
        if tmp > K: #すでにK個以上の0以外の数を使っているとき
            continue
        else:
            if tmp == K: #ちょうどK個使っている時
                dp1[i + 1][tmp] += 1 #0を使うしかない
            else:
                dp1[i + 1][tmp] += 1 #0を使うしかない
                dp1[i + 1][tmp + 1] += (a - 1) #N以下を確定させるためaは使えない

ans = dp1[n][K]
if dp2[n] == K:
    ans += 1

print (ans)

# print (dp1)
# print (dp2)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = input()
    k = int(input())

    # 桁DP
    def digit_DP(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]

    print(digit_DP(n, k))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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


# digit DP
def digit_dp(S,K):
    L = len(S)
    # dp[i][0] = 今のところぴったり
    # dp[i][1] = すでにSより小さいと確定している
    dp = [[[0 for k in range(K+1)] for j in range(2)] for i in range(L+1)]
    dp[0][0][0] = 1

    for i in range(L):
        D = int(S[i])
        for j in range(2):
            for d in range((9 if j else D)+1):
                for k in range(K+1):
                    if d != 0:
                        if k == K:
                            continue
                        dp[i+1][j or d<D][k+1] += dp[i][j][k]
                    else:
                        dp[i+1][j or d<D][k] += dp[i][j][k]

    return dp[L][0][K] + dp[L][1][K]         # 非負整数の数え上げ(0を含む)

print(digit_dp(S,K))

Submission status: Accepted

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def search(d, k, isLess):
    if k == K:
        return 1
    if d == len(N):
        return 0

    n = int(N[d])

    if isLess:
        return search(d + 1, k, isLess) + search(d + 1, k + 1, isLess) * 9

    ret = 0
    for i in range(n + 1):
        ret += search(d + 1, k + (1 if i > 0 else 0) , isLess or (i < n))
    return ret

print(search(0, 0, False))

Submission status: Accepted

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

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

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

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

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

        for k in range(K,-1,-1):
            dpsm[i][k]+=dpsm[i-1][k]
            dpsm[i][k]+=dp[i-1][k]
          
print(dp[-1][-1]+dpsm[-1][-1])

Submission status: Accepted

Solution code:
import math
import numpy as np
import queue
from collections import deque
import heapq

def cmb(n,r):
    c = 1
    for i in range(r):
        c *= (n-i)
    for i in range(r):
        c //= (i+1)
    return c

n = input()
k = int(input())
ln = len(n)
ans = 0

nn0 = 0
for i in range(ln):
    if int(n[i]) > 0:
        ans += cmb(ln-i-1,k-nn0)*(9**(k-nn0))
        nn0 += 1
        ans += (int(n[i])-1)*cmb(ln-i-1,k-nn0)*(9**(k-nn0))
    if nn0 == k:
        ans += 1
        break

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    n=len(s)
    K=int(input())
    dp_0=[[0]*(K+1) for _ in range(n+1)]
    dp_1=[[0]*(K+1) for _ in range(n+1)]
    dp_0[0][0]=1 
    for i in range(n):
        for j in range(K+1):
            for k in range(2):
                nd=int(s[i])-0
                for d in range(10): 
                    ni=i+1
                    nj=j
                    if d!=0:nj+=1
                    if nj>K:continue
                    if k==0:
                        if d>nd:continue
                        if d<nd:dp_1[ni][nj]+=dp_0[i][j]
                        else:dp_0[ni][nj]+=dp_0[i][j]
                    else:dp_1[ni][nj]+=dp_1[i][j]
    print(dp_0[n][K]+dp_1[n][K])

if __name__=='__main__':
    main()

Submission status: Accepted

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

dp = [[[0 for j in range(L + 10)] for i in range(L + 10)] for _ in range(2)]
dp[0][0][0] = 1

for i in range(L):
    Ni = int(N[i])
    for j in range(L):
        if Ni == 0:
            dp[0][i + 1][j + 0] += dp[0][i][j + 0] * 1
            dp[0][i + 1][j + 1] += dp[0][i][j + 0] * 0
            dp[1][i + 1][j + 0] += dp[0][i][j + 0] * 0 + dp[1][i][j + 0] * 1
            dp[1][i + 1][j + 1] += dp[0][i][j + 0] * 0 + dp[1][i][j + 0] * 9
        else:
            dp[0][i + 1][j + 0] += dp[0][i][j + 0] * 0
            dp[0][i + 1][j + 1] += dp[0][i][j + 0] * 1
            dp[1][i + 1][j + 0] += dp[0][i][j + 0] * 1 + dp[1][i][j + 0] * 1
            dp[1][i + 1][j + 1] += dp[0][i][j + 0] * (Ni - 1) + dp[1][i][j + 0] * 9
#print(dp[0])
#print(dp[1])

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

Submission status: Accepted

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

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

for N in range(2,len(str(n))+1):
    for num in range(10):
        for K in range(1,4):
            if num!=0:
                if num<int(str(n)[N-1]):
                    dp0[N][K]+=dp0[N-1][K-1]+dp1[N-1][K-1]
                elif num==int(str(n)[N-1]):
                    dp0[N][K]+=dp0[N-1][K-1]
                    dp1[N][K]+=dp1[N-1][K-1]
                else:
                    dp0[N][K]+=dp0[N-1][K-1]
            else:
                if int(str(n)[N-1])>0:
                    dp0[N][K]+=dp0[N-1][K]+dp1[N-1][K]
                elif int(str(n)[N-1])==0:
                    dp1[N][K]+=dp1[N-1][K]
                    dp0[N][K]+=dp0[N-1][K]
#print(dp0)
#print(dp1)
print(dp1[-1][k]+dp0[-1][k])

Submission status: Accepted

Solution code:
def solve():
    N = input()
    K = int(input())
    l = len(N)
    dp = [[[0]*(K+2) for i in range(2)] for j in range(l+1)]
    dp[0][False][0] = 1 

    for i in range(l):
        for smaller in [False,True]:
            for k in range(K+1):
                for x in range(10 if smaller else int(N[i])+1):
                    if x == 0:
                        dp[i+1][smaller or (x < int(N[i]))][k] += dp[i][smaller][k]
                    else:
                        dp[i+1][smaller or (x < int(N[i]))][k+1] += dp[i][smaller][k]
    
    print(dp[l][False][K] + dp[l][True][K])

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = input()
    length = len(N)
    K = int(input())

    # 左からi桁目まで見て，N以下が確定していて，0でない数字がk個ある数字の個数
    dp_1 = [[0] * (10) for _ in range(length)]

    # 左からi桁目まで見て，N以下が確定していなくて，0でない数字がk個ある数字の個数
    dp_2 = [[0] * (10) for _ in range(length)]

    dp_1[0][0] = 1
    dp_1[0][1] = int(N[0]) - 1

    dp_2[0][1] = 1

    for i in range(1, length):
        # 小さいのが確定しているものに対して，0以外のものを追加
        for k in range(1, K + 2):
            dp_1[i][k] += dp_1[i - 1][k - 1] * 9

        # 小さいものが確定しているものに対して，0を追加
        for k in range(0, K + 2):
            dp_1[i][k] += dp_1[i - 1][k]

        # 大小がわからないものから，小さいのが確定する
        if N[i] == "0":
            for k in range(K + 2):
                dp_2[i][k] += dp_2[i - 1][k]
        else:
            # 0を追加する
            for k in range(K + 2):
                dp_1[i][k] += dp_2[i - 1][k]

            # その他の数字を追加
            for k in range(1, K + 2):
                dp_1[i][k] += dp_2[i - 1][k - 1] * (int(N[i]) - 1)

            # 依然として大小関係がわからない
            for k in range(1, K + 2):
                dp_2[i][k] += dp_2[i - 1][k - 1]

    ans = dp_1[-1][K] + dp_2[-1][K]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
  s=input()
  k=int(input())
  n=len(s)
  def dp(i,j,smaller):
    # i桁目以降について、0以外の値を残りj個使用可能という状況を考える。i桁目までは決定している。残りn-i桁
    # このときi桁目までの部分が「等しい」か「strict に小さくなっている」かを smaller フラグによって分岐する。
    if n==i: # 0でない数字をk個つかえなかったパターン。
      return 0 if j>0 else 1
    if smaller:# 残りのn-i桁の中からj桁選び好きな数字にできる。j桁以外はすべて0
      if j==0:
        return 1
      elif j==1:
        return (n-i)*9
      elif j==2:
        return ((n-i)*(n-i-1))//2*9**2
      elif j==3:
        return ((n-i)*(n-i-1)*(n-i-2))//6*9**3
    if j==0: # i桁目以降はすべて0で決まり
      return 1
    ret=0
    # i+1桁目が0なら0を使うしかない
    if s[i]=='0':
      ret+=dp(i+1,j,smaller)
    else:
      ret+=dp(i+1,j-1,smaller) # i+1桁目でsと同じ数字を使う
      ret+=(int(s[i])-1)*dp(i+1,j-1,True) # i+1桁目で0より大きくs未満の数字使う
      ret+=dp(i+1,j,True) # i+1桁目で0を使う。
    return ret
  print(dp(0,k,False))
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n = str(input())
p = int(input())

keta = len(n)
Dp = [[[0 for _ in range(2)] for _ in range(keta+1)]for _ in range(keta+1)]

Dp[0][0][1] = 1
10
for i in range(keta):
    for j in range(i+1):
        for k in range(10):
            if k == 0:
                if k < int(n[i]):
                    Dp[i+1][j][0] += Dp[i][j][0]
                    Dp[i+1][j][0] += Dp[i][j][1]
                    
                elif k == int(n[i]):
                    Dp[i+1][j][1] += Dp[i][j][1]
                    Dp[i+1][j][0] += Dp[i][j][0]
                
                else:
                    Dp[i+1][j][0] += Dp[i][j][0]
            
            else:
                if k < int(n[i]):
                    Dp[i+1][j+1][0] += Dp[i][j][0]
                    Dp[i+1][j+1][0] += Dp[i][j][1]
                elif k == int(n[i]):
                    Dp[i+1][j+1][1] += Dp[i][j][1]
                    Dp[i+1][j+1][0] += Dp[i][j][0]
                else:
                    Dp[i+1][j+1][0] += Dp[i][j][0]

if p > keta:
    print(0)
else:
    print(sum(Dp[-1][p]))

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


target = list(map(int, list(input())[:-1]))
k = inp()
# dp[digits][notzeros][smaller]
# dp[digits+1][notzeros][smaller]上からi桁目までで条件を満たす数の総数

dp = [[[0] * 2 for _ in range(k + 2)] for i in range(len(target) + 1)]
dp[0][0][0] = 1
for i in range(len(target)):
    for j in range(k + 1):
        for smaller in range(2):
            for x in range(10 if smaller else target[i] + 1):  # 未満なら10進数全て探索
                conditions = 1 if x != 0 else 0  # 条件

                dp[i + 1][j + conditions][smaller or x < target[i]]\
                    += dp[i][j][smaller]
    # print(dp)

ans = sum(dp[len(target)][k])
print(ans)
# print(dp)

Submission status: Accepted

Solution code:
from scipy import misc

N = int(input())
K = int(input())
d = len(str(N))
first = int(str(N)[0])
if K == 1:
    print(9*(d-1)+first)
elif K == 2:
    if d == 1:
        print('0')
    else:
        for i in range(1,d):
            if str(N)[i] != '0':
                second_dig = i+1
                second_num = int(str(N)[i])
                break
        else:
            second_dig = d
            second_num = 0
        print(((d-1)*(d-2)//2*81)+(first-1)*(d-1)*9+(d-second_dig)*9+second_num)
else:
    if K < 3:
        print('0')
    else:
        found_second = False
        found_third = False
        for i in range(1,d):
            if str(N)[i] != '0':
                if found_second == False:
                    second_dig = i+1
                    second_num = int(str(N)[i])
                    found_second = True
                else:
                    third_dig = i+1
                    third_num = int(str(N)[i])
                    found_third = True
                    break
        if found_second == False:
            print((d-1)*(d-2)*(d-3)//6*729+(first-1)*((d-1)*(d-2)//2*81))
        elif found_third == False:
            print((d-1)*(d-2)*(d-3)//6*729+(first-1)*((d-1)*(d-2)//2*81)+(second_num-1)*(d-second_dig)*9+(d-second_dig)*(d-second_dig-1)//2*81)
        else:
            print((d-1)*(d-2)*(d-3)//6*729+(first-1)*((d-1)*(d-2)//2*81)+(second_num-1)*(d-second_dig)*9+(d-second_dig)*(d-second_dig-1)//2*81+(d-third_dig)*9+third_num)

Submission status: Accepted

Solution code:
N,K=int(input()),int(input())
def f(n,k):
  if k<1: return 1
  if n<10:
    if k<2: return n
    return 0
  d,m=n//10,n%10
  return f(d,k-1)*m+f(d-1,k-1)*(9-m)+f(d,k)
print(f(N,K))

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
l = len(str(N))
dp = [[[0]*(K+1) for _ in range(2)] for _ in range(l+1)]
# dp[i][smaller][j]
# i: 調べている桁
# smaller: 未満フラグ(未満のとき1)
# j: 0以外の数がj回出た

dp[0][0][0] = 1
for i in range(l):
  n = int(str(N)[i])
  for j in range(2):
    for k in range(K+1):
      for m in range(10):
        # 今までは一致
        if j == 0 and m > n:
          continue
        if j == 0 and m == n:
          nj = 0 # 今回も一致
          if m == 0:
            nk = k # 0なら回数は増えない
          else:
            if k < K:
              nk = k + 1 # 0以外の数がK-1回以下しかでていないなら増やす
            else:
              nk = k
              continue
        if j == 0 and m < n:
          nj = 1
          if m == 0:
            nk = k
          else:
            if k < K:
              nk = k + 1
            else:
              nk = k
              continue

        # すでに未満
        if j == 1:
          nj = j
          if m == 0:
            nk = k
          else:
            if k < K:
              nk = k + 1
            else:
              nk = k
              continue

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

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

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
l = len(str(N))
dp = [[[0]*(K+2) for _ in range(2)] for _ in range(l+1)]
# dp[i][smaller][j]
# i: 調べている桁
# smaller: 未満フラグ(未満のとき1)
# j: 0以外の数がj回出た

dp[0][0][0] = 1
for i in range(l):
  n = int(str(N)[i])
  for j in range(2):
    for k in range(K+1):
      for m in range(10):
        # 今までは一致
        if j == 0 and m > n:
          continue
        if j == 0 and m == n:
          nj = 0 # 今回も一致
          if m == 0:
            nk = k # 0なら回数は増えない
          else:
            if k < K:
              nk = k + 1 # 0以外の数がK-1回以下しかでていないなら増やす
            else:
              nk = k
              continue
        if j == 0 and m < n:
          nj = 1
          if m == 0:
            nk = k
          else:
            if k < K:
              nk = k + 1
            else:
              nk = k
              continue

        # すでに未満
        if j == 1:
          nj = j
          if m == 0:
            nk = k
          else:
            if k < K:
              nk = k + 1
            else:
              nk = k
              continue

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

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

Submission status: Accepted

Solution code:
n = input()
k = int(input())
dp = [[[0] * (k + 2) for i in range(2)] for j in range(len(n) + 1)]
dp[0][0][0] = 1

for i in range(len(n)):
    value = int(n[i])
    for j in range(2):
        for l in range(k + 1):
            for d in range(10 if j == 1 else value + 1):
                dp[i + 1][1 if j == 1 else 1 if (d < value) else 0][l if d == 0 else l + 1] += dp[i][j][l]
print(dp[len(n)][0][k] + dp[len(n)][1][k])

Submission status: Accepted

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



dp = [[[0 for _ in range(5)] for _ in range(2)] for _ in range(N+1)]
dp[0][0][0] = 1
"""
遷移
dp[i][1][j] -> dp[i+1][1][j] : i-1桁目までに0以外の数字がj個あり、i桁目に0を入れた
dp[i][1][j] -> dp[i+1][1][j+1] : i-1桁目までに0以外の数字がj個あり、i桁目に0以外を入れた
dp[i][0][j] -> dp[i+1][1][j] : i-1桁目がSと一致していて、i-1桁目までに0以外の数字がj個あり、までに0以外の数字がj個あり、i桁目に0を入れた
dp[i][0][j] -> dp[i+1][1][j] : i-1桁目がSと一致していて、i-1桁目までに0以外の数字がj個あり、までに0以外の数字がj個あり、i桁目に0以外を入れた
dp[i][0][j] -> dp[i+1][0][j+?] : i桁目までSと一致。i桁目が0以外なら、?=1

"""

for i in range(N):
    for k in range(4):
        for j in range(10):
        


            if j == 0:
                 # i桁目に0をあてた
                dp[i+1][1][k] += dp[i][1][k]
            else:
                # i桁目に0以外をあてた
                dp[i+1][1][k+1] += dp[i][1][k]


            if j < int(S[i]):
                if j == 0:
                    dp[i+1][1][k] += dp[i][0][k]
                else:
                    dp[i+1][1][k+1] += dp[i][0][k]
            elif j == int(S[i]):
                if j == 0:
                    dp[i+1][0][k] += dp[i][0][k]
                else:
                    dp[i+1][0][k+1] += dp[i][0][k]


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

Submission status: Accepted

Solution code:
def solve():
    N = input()
    K = int(input())
    dp = [[[0]*(K+2) for i in range(2)] for j in range(len(N)+1)]
    dp[0][False][0] = 1

    for i in range(len(N)):
        for k in range(K+1):
            dp[i+1][True][k+1] += dp[i][True][k] * 9
            dp[i+1][True][k] += dp[i][True][k]

            if int(N[i]) > 0:
                dp[i+1][True][k+1] += dp[i][False][k] * (int(N[i]) - 1)
                dp[i+1][True][k] += dp[i][False][k]
            
            if int(N[i]) > 0:
                dp[i+1][False][k+1] = dp[i][0][k]
            else:
                dp[i+1][False][k] = dp[i][0][k]
    
    print(dp[-1][False][K] + dp[-1][True][K])

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = list(map(int, list(input()[:-1].decode())))
    N = len(n)
    k = int(input())

    dp = [[[0] * (k + 1) for _ in range(2)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(1, N + 1):
        num = n[i - 1]
        for j in range(k + 1):
            dp[i][1][j] += dp[i - 1][1][j]
            if num != 0:
                dp[i][1][j] += dp[i - 1][0][j]
            else:
                dp[i][0][j] += dp[i - 1][0][j]
            if j >= 1:
                dp[i][1][j] += 9 * dp[i - 1][1][j - 1]
                if num != 0:
                    dp[i][0][j] += dp[i - 1][0][j - 1]
                    dp[i][1][j] += (num - 1) * dp[i - 1][0][j - 1]

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

digit = len(str(n))
# dp[i桁まで検査済み][lessthan][0以外の個数]
dp = [[[0] * (k + 2) for i in range(2)] for j in range(digit + 1)]
dp[0][0][0] = 1

for a in range(1, digit + 1):
    digitvalue = int(str(n)[a - 1])
    for b in range(2):
        for c in range(k + 1):
            for d in range(10 if b == 1 else digitvalue + 1):
                dp[a][1 if b == 1 else 1 if (d < digitvalue) else 0][c if d == 0 else c + 1] += dp[a - 1][b][c]

print(dp[digit][0][k] + dp[digit][1][k])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
dp0 = [[0]*(k+1) for _ in range(len(n)+1)]
dp1 = [[0]*(k+1) for _ in range(len(n)+1)]
dp0[0][0] = 1
for i in range(len(n)):
    for j in range(k+1):
        if int(n[i]) == 0:
            dp0[i+1][j] += dp0[i][j]
        if int(n[i]) > 0:
            dp1[i+1][j] += dp0[i][j]
            if j < k:
                dp0[i+1][j+1] += dp0[i][j]
                dp1[i+1][j+1] += dp0[i][j]*(int(n[i])-1)
        if j < k:
            dp1[i+1][j+1] += dp1[i][j]*9
        dp1[i+1][j] += dp1[i][j]
print(dp0[len(n)][k]+dp1[len(n)][k])

Submission status: Accepted

Solution code:
import itertools
N = input()
K = int(input())
l = len(N)
S = list(map(int, N))
N = int(N)

if K == 1:
    ans = S[0] + 9*(l-1)
elif K == 2 and l >= 2:
    # 最大桁がN未満のとき
    ans = (S[0]-1)*9*(l-1)
    # 最大桁がNのとき
    for i in range(1, l):
        if S[0]*10**(l-1)+9*10**(l-i-1) <= N:
            ans += 9
        else:
            ans += S[i]
    # 最大桁が0のとき
    if l > K:
        ans += (l-1)*(l-2)//2*9**2
elif K == 3 and l >= 3:
    # 最大桁がN未満のとき
    ans = (S[0]-1)*(l-1)*(l-2)//2*9**2
    # 最大桁がNのとき
    for a, b in itertools.combinations(range(1, l), 2):
        if S[0]*10**(l-1)+9*10**(l-a-1) <= N:
            if S[0]*10**(l-1)+9*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += 9**2
            else:
                ans += 8*9 + S[b]
        else:
            if S[0]*10**(l-1)+S[a]*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += S[a]*9
            else:
                if S[a] == 0:
                    pass
                else:
                    ans += (S[a]-1)*9 + S[b]
    # 最大桁が0のとき
    ans += (l-1)*(l-2)*(l-3)//6*9**3
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

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)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() 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()

n = ni()
s = str(n)
K = ni()

dp = [[[0] * 2 for _ in range(K + 2)] for _ in range(len(s) + 1)]
dp[0][0][0] = 1
for i in range(len(s)):
    for j in range(K + 1):
        for k in range(2):
            dmax = 9 if k else int(s[i])
            for d in range(dmax + 1):
                ni = i + 1
                nj = j + (d != 0)
                nk = k | (d < dmax)
                dp[ni][nj][nk] += dp[i][j][k]

print(dp[len(s)][K][0] + dp[len(s)][K][1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

'''MEMO:

'''

def main(): 
    N = II()
    K = II()

    keta_N = len(str(N))

    ans = 0

    # 1桁の数
    if K == 1: ans += min(9, N)
    else: pass
    if N < 10:
        print(ans)
        return

    # 2桁の数
    if K == 1:
        for i in range(10, 100, 10):
            if i <= N:
                ans += 1
    elif K == 2:
        for i in range(10, 100, 1):
            if i%10 == 0:
                continue
            elif i <= N:
                ans += 1
    else: pass
    if N < 100:
        print(ans)
        return

    # 3桁以上, keta_N桁未満
    if K == 1:
        ans += 9 * (keta_N - 3)
    else:
        for keta in range(3, keta_N):
            if K == 2:
                ans += 9 * (keta-1) * 9
            else:
                ans += (9 * (keta-1) * (keta-2) * 9 * 9)//2

    # keta_N桁の数
    # すべて生成しても 10**5 個程度なので、すべて生成して N と比較してみる。
    if K == 1:
        for i in range(1, 10):
            if i * 10**(keta_N - 1) <= N:
                ans += 1

    elif K == 2:
        for i in range(1, 10):
            for j in range(1, 10):
                for k in range(0, keta_N-1):
                    if i * 10**(keta_N - 1) + j * 10**k <= N:
                        ans += 1

    elif K == 3:
        for i in range(1, 10):
            if i < int(str(N)[0]):  # 10**7 のループなので愚直で回るはずだけれど、ちょっと高速化。
                ans += ((keta_N - 1) * (keta_N - 2) * 9 * 9)//2
                continue
            elif i > int(str(N)[0]):
                break
            for j in range(1, 10):
                for k in range(0, keta_N-1):
                    for l in range(1, 10):
                        for m in range(0, keta_N-1):
                            if k <= m: continue
                            if i * 10**(keta_N - 1) + j * 10**k + l * 10**m <= N:
                                ans += 1

    print(ans)

main()

Submission status: Accepted

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

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

# dp[i][x][flg]: 上からi桁目までが確定した段階で、0でない数字がx個あるような数字の個数
#    flg 0: 今作成している数字がN未満であることが確定していない
#    flg 1: 今作成している数字がN未満であることが確定している
dp[0][0][0] = 1

for i in range(len(N)):
    num = int(N[i])  # Nの上からi桁目の数字
    for x in range(K+1):
        if num == 0:
            dp[i+1][x][0] += dp[i][x][0]
            dp[i+1][x][1] += dp[i][x][1]
            if x >= 1:
                dp[i+1][x][1] += dp[i][x-1][1]*9
        else:  # num != 0
            dp[i+1][x][1] += dp[i][x][0] + dp[i][x][1]
            if x >= 1:
                dp[i+1][x][0] += dp[i][x-1][0]
                dp[i+1][x][1] += dp[i][x-1][0]*(num-1) + dp[i][x-1][1]*9
    # print(i, dp[i+1])


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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = read().split()

    N = list(map(int,N))
    K = int(K)
    max_i = len(N)
    dp2 = [0] * max_i
    r = 0
    for i, v in enumerate(N):
        if v != 0:
            r += 1
        dp2[i] = r

    dp1 = [[0] * (K+1) for _ in range(max_i)]

    dp1[0][1] = int(N[0]-1)
    dp1[0][0] = 1
    for i in range(1, max_i):
        for j in range(0, K+1):
            if j == 0:
                dp1[i][j] += dp1[i - 1][j]
            else:
                dp1[i][j] += dp1[i - 1][j] + dp1[i - 1][j - 1] * 9
        if N[i] == 0:continue
        if dp2[i-1] <= K:
            dp1[i][dp2[i-1]] += 1
        if dp2[i-1] < K:
            dp1[i][dp2[i-1]+1] += N[i] - 1
    plus = 0
    if dp2[-1] == K:
        plus = 1
    print(dp1[max_i-1][K] + plus)




if __name__ == "__main__":
    run()