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:
from functools import lru_cache
N = int(input())
K = int(input())
@lru_cache(None)
def f(n,k):
  if k<0:
    return 0
  if n<10:
    if k>1:
      return 0
    elif k==1:
      return n
    elif k==0:
      return 1
  a, b = divmod(n,10)
  m = 9*f(a-1,k-1)+f(a,k)+b*(f(a,k-1)-f(a-1,k-1))
  return m
print(f(N,K))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read

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


def count(d, k):
  if k == 0:
    return 1
  elif k == 1:
    return d
  elif k == 2:
    return d * (d - 1) // 2
  else:
    return d * (d - 1) * (d - 2) // 6


def solve(n, k):
  if n == 0 and k > 0:
    return 0
  if k == 0:
    return 1
  digit = len(str(n))
  res = 0
  if digit > k:
    res += count(digit - 1, k) * (9 ** k)
  a = 10 ** (digit - 1)
  d, mod = n // a, n % a
  res += count(digit - 1, k - 1) * (9 ** (k - 1)) * (d - 1)
  res += solve(mod, k - 1)
  return res


print(solve(n, k))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read

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


def count(d, k):
  if k == 0:
    return 1
  elif k == 1:
    return d
  elif k == 2:
    return d * (d - 1) // 2
  else:
    return d * (d - 1) * (d - 2) // 6


def solve(n, k):
  digit = len(str(n))
  if digit == 0 and k > 0:
    return 0
  if k == 0:
    return 1
  res = 0
  if digit > k:
    res += count(digit - 1, k) * (9 ** k)
  a = 10 ** (digit - 1)
  d, mod = n // a, n % a
  res += count(digit - 1, k - 1) * (9 ** (k - 1)) * (d - 1)
  res += solve(mod, k - 1)
  return res


print(solve(n, k))

Submission status: Accepted

Solution code:
n=input()
k=int(input())
dp=[[[0]*(k+2) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0]=1
for i,c in enumerate(n):
	c=int(c)
	for f in range(2):
		for j in range(k+1):
			for l in range(10*f or c+1):
				dp[i+1][f or l<c][j+(l>0)]+=dp[i][f][j]
print(dp[-1][0][k]+dp[-1][1][k])

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

import numpy as np

MOD = 10 ** 9 +7

n,m = map(int,read().split())
  
@lru_cache(None)
def F(N, K):

    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:
        ret += F(q,K-1)*r
        ret += F(q-1,K-1)*(9-r)
    
    ret +=F(q,K)
    return ret

print(F(n,m))

Submission status: Accepted

Solution code:
N = input()
K = int(input())
n0 = int(N[0])

# 数値Nから,1の位の位置をp1とする[keta]桁の部分数値が全て0であるか
def if_part_zero (N, p1, keta):
  partnum = 0
  beki = keta - 1
  for i in range(p1 - keta + 1, p1 + 1):
    if int(N[i]) > 0:
      return False
  return True


t = 0
if (K == 1):
  t = n0 + (len(N) - 1) * 9

if (K == 2):
  enough = 0
  for i in range(0, len(N) - 1):
    if i > 0:
      pattern1 = 9
      enough = 1
    else:
      pattern1 = n0
    for j in range(i + 1, len(N)):
      if enough == 1 or if_part_zero(N, j - 1, j - i - 1) == False:
        pattern2 = 9
      else:
        pattern2 = int(N[j])
      # print ("i=" + str(i) + " j=" + str(j) + " p=" + str((pattern1 - 1) * 9 + pattern2))
      t += (pattern1 - 1) * 9 + pattern2
    
if (K == 3):
  enough1 = 0
  enough2 = 0
  for i in range(0, len(N) - 2):
    if i > 0:
      pattern1 = 9
      enough1 = 1
    else:
      pattern1 = n0
    for j in range(i + 1, len(N) - 1):
      if enough1 == 1 or if_part_zero(N, j - 1, j - i - 1) == False:
        pattern2 = 9
        enough2 = 1
      else:
        pattern2 = int(N[j])
      if pattern1 == 1 and pattern2 == 0:
        continue
      for k in range(j + 1, len(N)):
        if enough1 == 1 or enough2 == 1 or if_part_zero(N, k - 1, k - j - 1) == False:
          pattern3 = 9
        else:
          pattern3 = int(N[k])
        
        # print ("1=" + str(pattern1) + " 2=" + str(pattern2) + " 3=" + str(pattern3) + " p=" + str(((pattern1 - 1) * 9 + pattern2 - 1) * 9 + pattern3))
        t += ((pattern1 - 1) * 9 + pattern2 - 1) * 9 + pattern3

print (t)

Submission status: Accepted

Solution code:
n = list(map(int, list(input())))
k = int(input())

N = len(n)

a = [[0 for _ in range(k+1)] for _ in range(len(n)+1)]
b = [[0 for _ in range(k+1)] for _ in range(len(n)+1)]
b[0][0] = 1

for i, x in enumerate(n):
    a[i+1][0] = a[i][0] + b[i][0]
    for j in range(1, k+1):
        temp = a[i][j-1] * 9 + a[i][j]
        if x > 0:
            temp += b[i][j] + b[i][j-1] * (x-1)
        a[i+1][j] = temp
        if x == 0:
            b[i+1][j] = b[i][j]
        else:
            b[i+1][j] = b[i][j-1]

#print(a)
#print(b)

print(a[N][k] + b[N][k])

Submission status: Accepted

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

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

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

for i in range(len(N)):
    for smaller in range(2):
        for j in range(K+1):
            for x in range(10 if smaller==1 else int(N[i])+1):
                dp[i+1][smaller or (x < int(N[i]))][j+1 if x!=0 else j]+=dp[i][smaller][j]
print(dp[len(N)][1][K]+dp[len(N)][0][K])

Submission status: Accepted

Solution code:
from sys import stdin
from functools import lru_cache

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


n = int(input())
k = int(input())
print(solver(n,k))

Submission status: Accepted

Solution code:
from sys import stdin
from functools import lru_cache

@lru_cache(None)
def solver(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    # divmod : 商と余りを両方取れる
    m, r = divmod(N,10)
    ans = 0
    if K >= 1:
        # 1の位が nonzero
        ans += solver(m, K-1) * r
        ans += solver(m-1, K-1) * (9-r)
    # 1の位が zero
    ans += solver(m, K)
    return ans


if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = solver(data[0][0], data[1][0])
    print(result)

Submission status: Accepted

Solution code:
def f(N, K):
    M, R = N // 10, N % 10
    if K == 0:
        return 1
    elif M == 0 and K == 1:
        return R
    elif M == 0 and K != 1:
        return 0
    else:
        return R * f(M, K-1) + (9-R) * f(M-1, K-1) + f(M, K)


N = int(input())
K = int(input())
print(f(N, K))

Submission status: Accepted

Solution code:
x=input()
L=len(x)
N=[]
for l in range(L):
  N.append(int(x[l]))
N.insert(0,0) 
K=int(input())
dp0=[]
dp1=[]
for l in range(L+1):
  dp0.append([0]*(K+1))
  dp1.append([0]*(K+1))
dp1[0][0]=1
for l in range(1,L+1):
  dp0[l][0]=1
for i in range (1,L+1):
  for j in range(1,K+1):
    if N[i]==0:
      dp0[i][j]=dp0[i-1][j]+9*dp0[i-1][j-1]
      dp1[i][j]=dp1[i-1][j]
    else:
      dp0[i][j]=dp0[i-1][j]+9*dp0[i-1][j-1]+(N[i]-1)*dp1[i-1][j-1]+dp1[i-1][j]
      dp1[i][j]=dp1[i-1][j-1]
print(dp0[L][K]+dp1[L][K])

Submission status: Accepted

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

def f(n,k):
  if len(n) == 1:
    if k == 1:
      return n[0]
    else:
      return 0
  else:
    r = n[-1]
    m = n[:-1]
    m2 = m.copy()
    m2[-1] = m2[-1] - 1
    for i in range(len(m)):
      if m2[-i] < 0:
        m2[-i] += 10
        m2[-i-1] = m2[-i-1] - 1
    if k == 1:
      m = n[:-1]
      return f(m,1) + 9
    else:
      return f(m,k) + f(m,k-1) * r + f(m2,k-1) * (9-r)
    
print(f(N,K))

Submission status: Accepted

Solution code:

# 桁DP問題
N = int(input())
K = int(input())

dp = [[[0,0] for _ in range(4)] for _ in range(101)]

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

# i = Nの●桁目
# j = 0以外の数字を何回利用しているか
# k == 0 Nを超えないように注意が必要
# k == 1 N以下が保証されている

keta = len(str(N))
for i in range(keta):
  for j in range(4):
    for k in range(2):
      num = int(str(N)[i])

      for n in range(10):
        ni, nj, nk = i+1, j, k

        if n != 0:
          nj += 1 # 0以外の数字を利用した数が増えた
        if nj > K: 
          continue # すでにKを使い切っているときはカウントしない
        if k == 0:
          if n > num:
            continue # Nを超えているので飛ばす
          if n < num:
            nk = 1 # 何でもOK

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

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

Submission status: Accepted

Solution code:
N = input()
K = int(input())
dp= [[[0]*2 for i in range(len(N)+1)] for _ in range(len(N)+1)]
if len(N)<K:
  print(0)
  exit()
dp[0][0][0]=1
for i in range(len(N)):
  for j in range(len(N)):
    if int(N[i])!=0:
      dp[i+1][j+1][1]+=dp[i][j][1]*9+dp[i][j][0]*(int(N[i])-1)
      dp[i+1][j][1] += dp[i][j][1]+dp[i][j][0]
      dp[i+1][j+1][0] += dp[i][j][0] 
    if int(N[i])==0:
      dp[i+1][j+1][1] += dp[i][j][1]*9
      dp[i+1][j][1] += dp[i][j][1]
      dp[i+1][j][0] += dp[i][j][0]
print(dp[len(N)][K][0]+dp[len(N)][K][1])

Submission status: Accepted

Solution code:
import numpy as np

N = input()
K = int(input())
lt,eq = 0,1
dp = np.zeros((101,2,5),dtype=int)

dn = len(N)
dp[0][eq][0] = 1
for i in range(dn):
    di = ord(N[i]) - ord('0')
    for k in range(K+1):
        dp[i+1][lt][k] = dp[i][lt][k] * 1 + dp[i][eq][k] * (1 if di >= 1 else 0)
        if k:
            dp[i+1][lt][k] += dp[i][lt][k-1] * 9 + dp[i][eq][k-1] * max(0,di-1)
        if dp[i][eq][k]:
            dp[i+1][eq][k+(di>0)] = 1

print(int(dp[dn][lt][K] + dp[dn][eq][K]))

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)]

dp0[0][0] = 1

n = []
for i in N:
    n.append(int(i))

for i in range(L):
    D = n[i]
    for j in range(K + 1):
        if D == 0:
            dp0[i + 1][j] += dp0[i][j]
            dp1[i + 1][j] += dp1[i][j]
            if j < K:
                dp1[i + 1][j + 1] = dp1[i][j] * 9
        else:
            dp1[i + 1][j] += (dp0[i][j] + dp1[i][j])
            if j < K:
                dp0[i + 1][j + 1] += dp0[i][j]
                dp1[i + 1][j + 1] += (D - 1) * dp0[i][j]
                dp1[i + 1][j + 1] += 9 * dp1[i][j]

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

Submission status: Accepted

Solution code:

#dp[i][k] : i番目まで見て、0でない数がk個出現しているときの組合せ
#dp0[][] : N以下であるか未確定、dp1[][] = N以下が確定

#例:1以上N以下の整数であって、0でない数字がちょうどK個あるような個数

def main(N,K):
    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, n in enumerate(N):
        for k in range(K + 1):
            #確認中の桁が0の場合
            if n == '0':
                dp0[i+1][k] += dp0[i][k]
                dp1[i+1][k] += dp1[i][k]
                #k < Kの場合
                if k < K:
                    dp1[i + 1][k + 1] += 9 * dp1[i][k]
            #確認中の桁が0以外の場合
            else:
                if k < K:
                    dp0[i+1][k+1] += dp0[i][k]
                    dp1[i+1][k+1] += (int(n) - 1) * dp0[i][k]
                    dp1[i+1][k+1] += 9 * dp1[i][k]

                dp1[i+1][k] += dp0[i][k]
                dp1[i+1][k] += dp1[i][k]
    print(dp0[-1][K] + dp1[-1][K])

N = input()
K = int(input())
main(N,K)

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize = None)
def rec(digit, flag, k):
    limit = int(N[digit])
    if k > K:
        return 0
    if digit == len(N) - 1:
        if k == K:
            return 1
        elif k == K - 1:
            return limit if flag else 9
        else:
            return 0
    if flag:
        if limit == 0:
            return rec(digit + 1, 1, k)
        else:
            return rec(digit + 1, 0, k + 1) * (limit - 1) + rec(digit + 1, 1, k + 1) + rec(digit + 1, 0, k)
    else:
        return rec(digit + 1, 0, k + 1) * 9 + rec(digit + 1, 0, k)

N = input()
K = int(input())
print(rec(0, 1, 0))

Submission status: Accepted

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

# dp[i][k] := i番目みて、0でない数がk個出現しているときの通り数
# dp0 := N以下であることが未確定, dp1 := N以下であることが確定
dp0 = [[0] * (K + 1) for i in range(N_digit + 1)]
dp1 = [[0] * (K + 1) for i in range(N_digit + 1)]
dp0[0][0] = 1

for i, n in enumerate(N):
    for k in range(K + 1):
        if n == '0':
            dp0[i + 1][k] += dp0[i][k]
            dp1[i + 1][k] += dp1[i][k]
            if k < K:
                dp1[i + 1][k + 1] += 9 * dp1[i][k]

        else:
            if k < K:
                dp0[i + 1][k + 1] += dp0[i][k]
                dp1[i + 1][k + 1] += (int(n) - 1) * dp0[i][k]
                dp1[i + 1][k + 1] += 9 * dp1[i][k]

            dp1[i + 1][k] += dp0[i][k]
            dp1[i + 1][k] += dp1[i][k]

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

Submission status: Accepted

Solution code:
n=int(input())
l=len(str(n))
k=int(input())
dp=[[[0]*(k+1) for _ in range(2)] for _ in range(l+1)]
dp[0][1][0]=1
for pos in range(l):
  num=int(str(n)[pos])
  for i in range(10):
    if i==0:
      for count in range(k+1):
        if num==0:
          dp[pos+1][1][count]+=dp[pos][1][count]
          dp[pos+1][0][count]+=dp[pos][0][count]
        else:
          dp[pos+1][0][count]+=(dp[pos][0][count]+dp[pos][1][count])
    elif i<num:
      for count in range(k):
        dp[pos+1][0][count+1]+=(dp[pos][0][count]+dp[pos][1][count])
    elif i==num:
      for count in range(k):
        dp[pos+1][1][count+1]+=dp[pos][1][count]
        dp[pos+1][0][count+1]+=dp[pos][0][count]
    else:
      for count in range(k):
        dp[pos+1][0][count+1]+=dp[pos][0][count]
print(dp[l][0][k]+dp[l][1][k])

Submission status: Accepted

Solution code:
from math import factorial
N = int(input())
K = int(input())
S = list(map(int,str(N))) #桁数
ans = 0
digit = len(S)
k = K

def D(i,j): 
    if i >= j:
        return (9**j) * (factorial(i) // (factorial(i - j) * factorial(j)))
    else:
        return 0

if K > len(S):
    print(0)
    exit()

for i in range(digit):
    digit -= 1
    if int(S[i]) == 0:
        if K == len(S):
            print(0)
            exit()
        continue
    ans += D(digit,k)
    k -= 1
    if k == 0:
        ans += S[i]
        break
    ans += (int(S[i]-1))*D(digit,k)
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    k = I()
    a = [int(c) for c in str(n)]
    l = len(a)
    dp = [[[0]*(k+1) for j in range(2)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        cp = dp[i]
        np = dp[i+1]
        c = a[i]
        if c == 0:
            for j in range(2):
                for ck in range(k+1):
                    np[j][ck] += cp[j][ck]
        else:
            for j in range(2):
                for ck in range(k+1):
                    np[1][ck] += cp[j][ck]

        for v in range(1,10):
            if v == c:
                for ck in range(k):
                    np[0][ck+1] += cp[0][ck]
                    np[1][ck+1] += cp[1][ck]
            elif v < c:
                for ck in range(k):
                    np[1][ck+1] += cp[0][ck]
                    np[1][ck+1] += cp[1][ck]
            else:
                for ck in range(k):
                    np[1][ck+1] += cp[1][ck]

    r = dp[l][0][k] + dp[l][1][k]
    return r


print(main())

Submission status: Accepted

Solution code:
n=input()
k=int(input())
l=len(n)
dp=[[[0]*(k+1) for i in range(2)] for i in range(l+1)]
#len,satu?,k
dp[0][0][0]=1#first
for i in range(1,l+1):
    x=int(n[i-1])
    for j in range(k+1):
        dp[i][1][j]+=dp[i-1][1][j]
        if j!=0:
            dp[i][1][j]+=9*dp[i-1][1][j-1]
            if x>0:
                dp[i][1][j]+=(x-1)*dp[i-1][0][j-1]
        if x!=0:
            dp[i][1][j]+=dp[i-1][0][j]
        if x==0:
            dp[i][0][j]+=dp[i-1][0][j]
        elif j>0:
            dp[i][0][j]+=dp[i-1][0][j-1]

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

Submission status: Accepted

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

dp = [[[0 for i in range(2)] for j in range(4)] for k in range(105)]

n = len(s)

dp[0][0][0] = 1
# print(dp)
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])  # 今の桁の数
            for d in range(10):
                ni = i + 1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
# print(dp)
ans = dp[n][K][0] + dp[n][K][1]
print(ans)

Submission status: Accepted

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

DP=[[[0]*(K+2) for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(K+1):
            for k in range(num+1):
                if k==0:
                    DP[i][flag or k<num][j] +=DP[i-1][flag][j]
                else:
                    DP[i][flag or k<num][j+1] +=DP[i-1][flag][j]

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

Submission status: Accepted

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

#kが小さい
#100桁から2か所,1~9二回選択
#ちょうどk個

ans = 0
l = len(n_) 
ans += int(n_[0])+9*(l-1)
if k==1:
    print(ans)
    exit()
ans = 0
ans += 9*9*(l-2)*(l-1)//2
ans += (int(n_[0])-1)*9*(l-1)
tmp = int(n_[0])*10**(l-1)
for j in range(1,10):
    for i in range(len(n_)):
        if n>=tmp+j*10**i:
            ans += 1
if k==2:
    print(ans)
    exit()
    
ans = 0

ans += 9*9*9*(l-2)*(l-1)*(l-3)//6
ans += (int(n_[0])-1)*9*9*(l-1)*(l-2)//2
tmp = int(n_[0])*10**(l-1)
for j in range(1,10):
    for k in range(1,10):
        for i in range(len(n_)):
            for h in range(i):
                if n>=tmp+j*10**i+k*10**h:
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = input().rstrip()
m = int(input())

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

for i in range(len(n)):
    for j in range(4):
        for k in range(2):
            nd = ord(n[i]) - ord('0')
            for d in range(10):
                ni = i + 1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if nj > m:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
            
print(dp[len(n)][m][0] + dp[len(n)][m][1])

Submission status: Accepted

Solution code:
from math import factorial
def comb(n,k):
    if n>=k:
        return int(factorial(n)/(factorial(k)*factorial(n-k)))
    else:
        return 0

def calc(a,k):
        t = len(a)
        t1 = len(a) - 1
        if k<1 or t == 0:
            return 0
        else:
            if a[t1]>0:
                ans = (9**k)*comb(t1,k) + (9**(k-1))*(a[t1]-1)*comb(t1,k-1)
                ans+=calc(a[:(t-1)],k-1)
            else:
                ans = 0
                ans+=calc(a[:(t-1)],k)
            if a[-k]>=1 and k == 1:
               ans+=1
            return ans

n = int(input())
k = int(input())
number = []
while n:
    number.append(n%10)
    n//=10

t = len(number)
t1 = len(number) - 1

if t>=k:
    ans = 0
    ans += calc(number,k)
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
def comb(n,k):
    if n>=k:
        return int(factorial(n)/(factorial(k)*factorial(n-k)))
    else:
        return 0


def calc(a,k):
        t = len(a)
        t1 = len(a) - 1
        if k<1 or t == 0:
            return 0
        else:
            if a[t1]>0:
                ans = (9**k)*comb(t1,k) + (9**(k-1))*(a[t1]-1)*comb(t1,k-1)
                ans+=calc(a[:(t-1)],k-1)
            else:
                ans = 0
                ans+=calc(a[:(t-1)],k)
            if a[-k]>=1 and k == 1:
               ans+=1
            return ans


n = int(input())
k = int(input())
number = []
while n:
    number.append(n%10)
    n//=10

t = len(number)
t1 = len(number) - 1

if t>=k:
    ans = 0
    ans += calc(number,k)
else:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
def comb(n,k):
    if n>=k:
        return int(factorial(n)/(factorial(k)*factorial(n-k)))
    else:
        return 0

n = int(input())
k = int(input())
number = []
while n:
    number.append(n%10)
    n//=10

t = len(number)
t1 = len(number) - 1

if t>=k:
    ans = 0
    def calc(a,k):
        t = len(a)
        t1 = len(a) - 1
        if k<1 or t == 0:
            return 0
        else:
            if a[t1]>0:
                ans = (9**k)*comb(t1,k) + (9**(k-1))*(a[t1]-1)*comb(t1,k-1)
                ans+=calc(a[:(t-1)],k-1)
            else:
                ans = 0
                ans+=calc(a[:(t-1)],k)
            if a[-k]>=1 and k == 1:
               ans+=1
            return ans
    ans += calc(number,k)
else:
    ans = 0
print(ans)

Submission status: Accepted

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

D = [[[0] * (k+1) for i in range(len(n))] for j in range(2)]

D[0][0][0] = 1
D[0][0][1] = int(n[0]) - 1
D[1][0][1] = 1
kk = 1

for i in range(1, len(n)):
    D[0][i][0] = D[0][i-1][0]
    for j in range(1, k+1):
        D[0][i][j] += D[0][i-1][j-1] * 9 + D[0][i-1][j]
    if n[i] == "0":
        if kk < k+1:
            D[1][i][kk] += D[1][i-1][kk]
    else:
        if kk < k+1:
            D[0][i][kk] += D[1][i-1][kk]
        if kk+1 < k+1:
            D[1][i][kk+1] += D[1][i-1][kk]
            D[0][i][kk+1] += D[1][i-1][kk] * (int(n[i]) - 1)
        kk += 1

print(D[0][-1][-1] + D[1][-1][-1])
# print(D)

Submission status: Accepted

Solution code:
from functools import lru_cache

N = int(input())
K = int(input())
memo = {}

@lru_cache(maxsize = 128)
def F(N, K):
    """
    F(N, K) = (1以上N以下で0でない桁がちょうどK個なものの個数)
    Nを一の桁から見ていくことで再帰で求める
    （例）F(314,3) = F(31,2)*4 + F(30,2)*5 + F(31,3)
                      = {F(3,1) + F(2,1)*8 + F(3,2)} * 4
                            + {F(2,1)*9 + F(3,2)} * 5
                            + {F(3,2) + F(2,2)*8 + F(3,3)}
                      = ...
    """
    r = int(str(N)[-1])
    M = (N - r) // 10
    if K == 0 and N >= 0:
        return 1
    elif K == 0 and N <= -1:
        return 0
    elif N <= 0:
        return 0
    else:
        return F(M, K-1) * r + F(M-1, K-1) * (9-r) + F(M, K)

print(F(N, K))

Submission status: Accepted

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

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

for i in range(len(n)):
    for j in range(4):
        for k in range(2):
            ntemp = int(n[i])
            for d in range(10):
                ni = i+1
                nj = j
                nk = k
                if d != 0: nj= nj+1
                if nj > K:continue
                if k == 0:
                    if d > ntemp:continue
                    if d < ntemp:nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
ans = dp[len(n)][K][0] + dp[len(n)][K][1]
print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n = onem()
k = onem()

s = str(n)

dp0 = [[0 for j in range(4)] for i in range(len(str(n))+1)]
dp1 = [[0 for j in range(4)] for i in range(len(str(n))+1)]

po = 0

dp0[0][0] = 0
dp1[0][0] = 1

for i in range(1,len(str(n))+1):
    point = i - 1
    np = int(s[point])
    po += 1 if np == 0 else 0

    dp0[i][0] = 1
    dp1[i][0] = 0

    dp0[i][1] = dp1[i-1][0]*(max(0,np-1)) + dp0[i-1][0]*9 + dp0[i-1][1] + ( dp1[i-1][1] if np != 0 else 0 )
    dp1[i][1] = 1 if i == 1 + po else 0

    dp0[i][2] = dp1[i-1][1] * (max(0,np-1)) + dp0[i-1][1] * (9) + dp0[i-1][2] + ( dp1[i-1][2] if np != 0 else 0 )
    dp1[i][2] = 1 if i == 2 + po else 0

    dp0[i][3] = dp1[i-1][2] * (max(0,np-1)) + dp0[i-1][2] * (9) + dp0[i-1][3] + ( dp1[i-1][3] if np != 0 else 0 )
    dp1[i][3] = 1 if i == 3 + po else 0

    


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

Submission status: Accepted

Solution code:
#most
N = int(input())
K = int(input())
n = list(map(int, str(N)))
dp = [[[0] * 5 for __ in range(2)] for _ in range(101)]
l = len(n)
dp[0][0][0] = 1
for i in range(l):
    for smaller in range(2):
        for j in range(4):
            for x in range((9 if smaller else n[i]) + 1):
                dp[i + 1][smaller or x < n[i]][j + 1 if x != 0 else j] += dp[i][smaller][j]
print(dp[l][0][K] + dp[l][1][K])

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(None)
def solve(n,k) :
  if n<=9:
    if k==0: return 1
    if k==1: return n
    return 0
  if k==0: return 1
  m, r = divmod(n, 10)
  return r*solve(m, k-1)+(9-r)*solve(m-1, k-1)+solve(m, k)

N = int(input())
K = int(input())
print(solve(N, K))

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(None)
def solve(n,k) :
  if n<=9:
    if k==0: return 1
    if k==1: return n
    return 0
  m = n//10
  r = n%10
  return r*solve(m, k-1)+(9-r)*solve(m-1, k-1)+solve(m, k)

N = int(input())
K = int(input())
print(solve(N, K))

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(None)
def solve(n,k) :
  if n<=9:
    if k==0: return 1
    if k==1: return n
    return 0
  m, r = divmod(n, 10)
  return r*solve(m, k-1)+(9-r)*solve(m-1, k-1)+solve(m, k)

N = int(input())
K = int(input())
print(solve(N, K))

Submission status: Accepted

Solution code:
#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N
#math.ceilで切り上げ
#dp = [[0] * 4 for i in range(3)] #2次元配列初期化
#dp = [[[0] * 2 for i in range(3)] for j in range(5)]

import math
import string

def intinput():
    return int(input())

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

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

N = str(intinput())
K = intinput()
s = len(str(N))
dp = [[[0] * 2 for i in range(4)] for j in range(s+1)]
dp[0][0][0] = 1
for h in range(1,s+1):
    dp[h][0][1] = 1
    for i in range(1,4):
        for j in range(0,2):
            if j == 1:      
                for k in range(0,10):
                    if int(N[h-1]) == 0:
                        dp[h][i][j] += dp[h-1][i][1] + dp[h-1][i-1][1]*9
                        break
                    if int(N[h-1]) > k:
                        if k == 0:
                            dp[h][i][j] += dp[h-1][i][0] + dp[h-1][i][1]
                        if k != 0:
                            dp[h][i][j] += dp[h-1][i-1][0] + dp[h-1][i-1][1]
                    if int(N[h-1]) <= k:
                        dp[h][i][j] += dp[h-1][i-1][1]
            if j == 0:
                if int(N[h-1]) == 0:
                    dp[h][i][j] += dp[h-1][i][0]
                else:
                    dp[h][i][j] += dp[h-1][i-1][0]

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

Submission status: Accepted

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

dp = [[[0]*(k+1) for _ in range(2)]for _ in range(nl+1)]
#dp[i][j][k] i:上からの桁数、j:smaller flag、k:0以外の数字の個数
dp[0][0][0] = 1

for i in range(nl):
  for j in range(2):
    for l in range(k+1):
      c = int(n[i])
      if j == 1:
        dp[i+1][j][l] += dp[i][j][l]
        if l < k:
          dp[i+1][j][l+1] += dp[i][j][l]*9
      else:
        if c == 0:#0しか選べない上にsmallを確定できない
          dp[i+1][0][l] += dp[i][j][l]
        else:
          dp[i+1][1][l] += dp[i][j][l]#cより確実に小さい0を使う。small確定
          if l < k:
            dp[i+1][1][l+1] += dp[i][j][l]*(c-1) #c以下の数字を使えばsmall確定
            dp[i+1][0][l+1] += dp[i][j][l] #cを使ったらsmall確定できない
            
print(dp[nl][0][k]+dp[nl][1][k])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
nl = len(n)#桁数
dp = [[[0] * (k + 1) for i in range(2)] for i in range(nl + 1)]
dp[0][0][0] = 1# 初期条件

# dp[i][j][k] i:桁数 j:smallフラグ 1はsmall確定、0はnと同じ値 k:ゼロ以外の数字を使った回数
for i in range(nl):
    for j in range(2):
        for l in range(k + 1): # lはK+1(つまりk)までの範囲にしても問題なし。下でl<kするから
            c = int(n[i])# 今調べている桁の数
            if j == 1:  # small確定の場合
                dp[i + 1][j][l] += dp[i][j][l]  # kの値が等しいので次の桁で0が来なければいけない
                if l < k:  # まだ0でない数の個数がkより少ない場合   ※比較する変数注意！
                    dp[i + 1][j][l + 1] += dp[i][j][l] * 9  # 次の桁で1~9を使う
            else:  # j==0のとき つまり現在まで調べている桁数の部分がnと一致している。
                if c == 0:
                    # cが0のときは0しか選べなく、small確定できない
                    dp[i + 1][0][l] += dp[i][j][l]
                else:
                    dp[i + 1][1][l] += dp[i][j][l]  # Cより小さい0を使う→small確定
                    if l < k: #※比較する変数注意！
                        dp[i + 1][1][l + 1] += dp[i][j][l] * (c - 1)  # c以外の数字を使う、small確定
                        dp[i + 1][0][l + 1] += dp[i][j][l]  # cを使う、small確定できない
print(dp[nl][1][k]+dp[nl][0][k])