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:
s = input()
n = len(s)
k = int(input())

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

for l in range(n):
    for m in range(k + 1):
        for o in range(2):
            nd = int(s[l])
            for d in range(10):
                nl, nm, no = l + 1, m, o
                if d != 0:
                    nm += 1
                if nm > k:
                    continue
                if 0 == o:
                    if d > nd:
                        continue
                    if d < nd:
                        no = 1
                dp[nl][nm][no] += dp[l][m][o]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

    for i in range(n_len):
        ni = int(N[i])
        for isLess in [0, 1]:
            for not_0 in range(K+1):
                num = 10 if isLess else ni + 1
                dp[i+1][isLess or 0 < ni][not_0] += dp[i][isLess][not_0]
                for j in range(1, num):
                    dp[i+1][isLess or j < ni][not_0+1] += dp[i][isLess][not_0]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
from functools import lru_cache

@lru_cache(maxsize=1000)
def dp(n, k): #0以上n以下の数で０でない数字がちょうどk個あるもの。
  if k == 0:
    return 1
  elif n == 0:
    return 0
  else:
    n = int(n)
    s = str(n)
    digit = len(s)
    m, fdigit = divmod(n,10)
    if m >= 1:
        return int(dp(m, k-1) * fdigit + dp(m-1, k-1)* (9-fdigit) + dp(m, k))
    elif k == 1:
        return n
    elif k == 2 or k == 3:
        return 0
    else:
        return 1
if K == 0:
    answer = dp(N, K)-1
else:
    answer = dp(N, K)
print(int(answer))

Submission status: Accepted

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

dig=len(str(N))

dp=[[[0,0,0,0] for _ in range(2)] for i in range(dig+1)]
#dp[i][j][k]は上からi桁目まで，tightかどうか，0ではない数の個数(0,1,2,3)

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


for i in range(1,dig):
    for j in range(2):
        if j==0:
            dp[i+1][j][0]=dp[i][j][0]
            dp[i+1][j][1]+=dp[i][j][0]*9+dp[i][j][1]
            dp[i+1][j][2]+=dp[i][j][1]*9+dp[i][j][2]
            dp[i+1][j][3]+=dp[i][j][2]*9+dp[i][j][3]
        if j==1:
            if N[i]=="0":
                for k in range(4):
                    dp[i+1][j][k]=dp[i][j][k]
            else:
                #tight to tight
                dp[i+1][j][1]=dp[i][j][0]
                dp[i+1][j][2]=dp[i][j][1]
                dp[i+1][j][3]=dp[i][j][2]
                
                #tight to not tight
                n=int(N[i])
                dp[i+1][j-1][1]+=dp[i][j][0]*(n-1) + dp[i][j][1]
                dp[i+1][j-1][2]+=dp[i][j][1]*(n-1) + dp[i][j][2]
                dp[i+1][j-1][3]+=dp[i][j][2]*(n-1) + dp[i][j][3]
                
            
ans=dp[-1][0][K]+dp[-1][1][K]
print(ans)

Submission status: Accepted

Solution code:
dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(105)]

s = input()
n = len(s)
K = int(input())

dp[0][0][0] = 1
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])
            for d in range(10):
                ni, nj, nk = i + 1, j, k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if 0 == k:
                    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:
N = int(input())
K = int(input())
def dp(n, k): #0以上n以下の数で０でない数字がちょうどk個あるもの。
  if k == 0:
    return 1
  elif n == 0:
    return 0
  else:
    n = int(n)
    s = str(n)
    digit = len(s)
    m, fdigit = divmod(n,10)
    if m >= 1:
        return int(dp(m, k-1) * fdigit + dp(m-1, k-1)* (9-fdigit) + dp(m, k))
    elif k == 1:
        return n
    elif k == 2 or k == 3:
        return 0
    else:
        return 1
if K == 0:
    answer = dp(N, K)-1
else:
    answer = dp(N, K)
print(int(answer))

Submission status: Accepted

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

# dp1 = the higest digit is 0, dp2 = the highest digit is not 0
dp1 = [[0] * (K+1) for _ in range(L+1)]
dp2 = [[0] * (K+1) for _ in range(L+1)]
for i in range(L+1):
    dp1[i][0] = 1
    for j in range(1, K+1):
        dp1[i][j] = dp1[i-1][j] + dp2[i-1][j]
        dp2[i][j] = 9 * (dp1[i-1][j-1] + dp2[i-1][j-1])
ans = dp1[L][K] + dp2[L][K]
d = K
for i in range(L):
    if N[i] != '0':
        ans -= dp2[L-i][d] * (9-int(N[i])) // 9
        d -= 1
    else:
        ans -= dp2[L-i][d]
    if d == 0:
        break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#Kが3種類なので、分岐を全て書く
#桁数をa、最上位の桁をbとし、その値で場合分け
#最上位が0場合、最上位が0以上b未満の場合(最上位が0は個数も0のため重複されない)、最上位がbで残りのa-1桁でK-1にして再帰
def ans(n,k):
  s=str(n)
  a=len(s)
  b=int(s[0])
  if(k==1):
    return 9*(a-1)+b
  elif(k==2):
    return int(81*(a-1)*(a-2)/2)+9*(b-1)*(a-1)+ans(n-b*10**(a-1),1)
  else:
    return int(729*(a-1)*(a-2)*(a-3)/6)+int(81*(b-1)*(a-1)*(a-2)/2)+ans(n-b*10**(a-1),2)

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

Submission status: Accepted

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

#print(N_str)
digit_N=len(N_str)

#dp[i][j]: j:digit, k:K
dp_eq=[]
dp_ne=[]
for i in range(digit_N):
  dp_eq.append([0]*(K+1))
  dp_ne.append([0]*(K+1))

#init
dp_eq[0][1]=1
dp_ne[0][1]=int(N_str[0])-1
for i in range(digit_N):
  dp_ne[i][0]=1

for j in range(1,digit_N):
  digit=int(N_str[j])
  for k in range(1,K+1):
    if digit==0:
      dp_ne[j][k]=dp_ne[j-1][k]+9*dp_ne[j-1][k-1]
      dp_eq[j][k]=dp_eq[j-1][k]
    else:
      dp_ne[j][k]=dp_ne[j-1][k]+9*dp_ne[j-1][k-1]+dp_eq[j-1][k]+(digit-1)*dp_eq[j-1][k-1]
      dp_eq[j][k]=dp_eq[j-1][k-1]
    
print(dp_ne[-1][K]+dp_eq[-1][K])

Submission status: Accepted

Solution code:
s=input()+"9";n=len(s);X=[0]*4;Y=[0]*4;
while n:
 n-=1;k=4
 while k:k-=1;a=int(s[n]);Y[k],X[k]=(X[k]+(a-1)*X[k-1]+Y[k-1]if a else Y[k],X[k]+9*X[k-1])if k else (1,1)
print(Y[int(input())])

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)):
    D = int(X[i])
    for j in range(2):
        for k in range(K + 1):
            for d in range((9 if j == 1 else D) + 1):
                if k + int(d != 0) <= K:
                    dp[i + 1][j | (d < D)][k + int(d != 0)] += dp[i][j][k] 
print(dp[-1][0][-1]+dp[-1][1][-1])

Submission status: Accepted

Solution code:
def main():
    a = input()
    b = int(input())
    n = len(a)

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

    for i in range(n):
        nd = int(a[i])
        for j in range(b+1):
            for k in range(2):
                for d in range(10):
                    ni = i+1
                    nj = j
                    nk = k
                    if d != 0:
                        nj += 1
                    if nj > b:
                        continue
                    if k == 0:
                        if d > nd:
                            continue
                        if d < nd:
                            nk = 1
                    dp[ni][nj][nk] += dp[i][j][k]

    ans = dp[n][b][0] + dp[n][b][1]
    print(ans)


main()

Submission status: Accepted

Solution code:
import math

def comb(n, r):
    if r < 0 or r > n:
        return 0

    if r == 1:
        return n
    elif r == 2:
        return n* (n - 1) / 2
    else:
        return n * (n - 1) * (n - 2) / 6

def solve(i, k, smaller):
    if i == N:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    if smaller:
        return comb(N - i, k) * math.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)
            icchi = solve(i + 1, k - 1, False)
            return int(zero + aida + icchi)

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

print(solve(0, K, False))

Submission status: Accepted

Solution code:
s=input()+"9";n=len(s);X=[(0,0)]*4;
while n:
 n-=1;k=4
 while k:k-=1;a=int(s[n]);X[k]=(X[k][0]+9*X[k-1][0],X[k][0]+(a-1)*X[k-1][0]+X[k-1][1]if a else X[k][1])if k else(1,1)
print(X[int(input())][1])

Submission status: Accepted

Solution code:
n=int(input())
m=len(str(n))
k=int(input())
N=[int(i) for i in str(n)]
dp0=[[0]*(k+1) for _ in range(m+1)]
dp1=[[0]*(k+1) for _ in range(m+1)]
dp1[0][0]=1
for i,e in enumerate(str(n)):
    e = int(e)
    for j in range(k+1):
        dp1[i+1][j]+=dp1[i][j]*(e==0)
        dp0[i+1][j]+=dp0[i][j]+dp1[i][j]*(e!=0)
        if j<k:
            dp1[i+1][j+1]+=dp1[i][j]*(e!=0)
            dp0[i+1][j+1]+=dp0[i][j]*9+dp1[i][j]*max(0,e-1)
print(dp1[m][k]+dp0[m][k])

Submission status: Accepted

Solution code:
s=input()*2;n=len(s)//2;X=[(0,0)]*4
for j in range(n+1):
 for k in range(3,-1,-1):
  a=int(s[n-j])
  X[k]=(X[k][0]+9*X[k-1][0],X[k][0]+(a-1)*X[k-1][0]+X[k-1][1]if a else X[k][1])if k else(1,1)
print(X[int(input())][1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=input()*2;n=len(s)//2;X=[(0,0)]*4
for j in range(n+1):
 for k in range(3,-1,-1):
  a=int(s[n-j])
  X[k]=(X[k][0]+9*X[k-1][0]if k else 1,(X[k][0]+(a-1)*X[k-1][0]+X[k-1][1]if k else 1)if a else X[k][1])
print(X[int(input())][1])

Submission status: Accepted

Solution code:
from functools import lru_cache

N=int(input())
K=int(input())
 
@lru_cache(None)
def F(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
#     assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    q,r = divmod(N,10)
    ret = 0
    if K >= 1:
        # 1の位が nonzero
        ret += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    # 1の位が zero
    ret += F(q, K)
    return ret
 
# F(100, 1), F(25, 2), F(314159, 2)
 
print(F(N, K))

Submission status: Accepted

Solution code:
s=input()*2;n=len(s)//2;X=[(0,0)]*4
for j in range(n+1):
 for k in range(3,-1,-1):
  a=int(s[n-j])
  if k>j+1:X[k]=(0,0)
  else:X[k]=(X[k][0]+9*X[k-1][0]if k else 1,(X[k][0]+(a-1)*X[k-1][0]+X[k-1][1]if k else 1)if a else X[k][1])
print(X[int(input())][1])

Submission status: Accepted

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

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

ans = dp[len(N)][K][0] + dp[len(N)][K][1]

print(ans)

Submission status: Accepted

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

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

dp1=[[0]*(k+2) for i in range(len(n)+1)]
dp1[0][0]=1
# i桁まで見て j個の１から９を使ってn以下確定したもの　dp0[i][j]
#                                  確定していないもの　dp1[i][j]
for i in range(len(n)):
    for j in range(k+1):
        x=int(n[i])
        if x!=0:
            # 0を立てる
            dp0[i+1][j]+=dp0[i][j]+dp1[i][j]
            # 0以外を立てる
            dp0[i+1][j+1]+=dp0[i][j]*9
            if dp1[i][j]!=0:
                dp0[i+1][j+1]+=x-dp1[i][j]
            dp1[i+1][j+1]+=dp1[i][j]
        else:
            # 0を立てる
            dp0[i+1][j]+=dp0[i][j]
            dp1[i+1][j]+=dp1[i][j]
            # 0以外を立てる
            dp0[i+1][j+1]+=dp0[i][j]*9

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

Submission status: Accepted

Solution code:
# ABC029-D
# N以下1の現れる回数

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

dp = [[[0, 0] for _ in range(5)] for _ in range(L+1)]
# dp[l][k][isless] = 上からl桁目まで読んだ時、0以外がk個あって、
# isless = 0　なら上からl桁の数が全て一致している
# isless = 1　なら一致せず、どこかの桁が小さい

dp[0][0][0] = 1
# 一番上の桁の上に0があるとみなす

for l in range(L):
    a = int(N[l])
    for isless in [0, 1]:
        for k in range(4):
            for num in range(10):
                # 次の桁が実際のものより小さいならisless = 1で確定
                if num < a:
                    if num != 0:
                        dp[l+1][k+1][1] += dp[l][k][isless]
                    else:
                        dp[l+1][k][1] += dp[l][k][isless] 
                # 次の桁が一致したならそれまでの状態を引き継ぐ
                # 超えてたらislessになっているもののみ通す
                elif num == a or isless:
                    if num != 0:
                        dp[l+1][k+1][isless] += dp[l][k][isless]
                    else:
                        dp[l+1][k][isless] += dp[l][k][isless]
#print(dp)
#ans = 0
#for k in range(L+1):
#    ans += k*(dp[L][k][1] + dp[L][k][0])
print(dp[L][K][1]+dp[L][K][0])

Submission status: Accepted

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

# まずNをもとにdp[0]を処理する
cnt=0
for l in range(1,L):
    if int(N[l-1])!=0:
        cnt+=1
    if cnt>3:
        break
    else:
        dp[0][cnt][l]=1


# 次にdp[1]を処理。
# 遷移としては
# dp[1][j-1][i-1]からdp[1][j][i]へは'1'から'9'が選ばれ*9
# dp[1][j][i-1]からdp[1][j][i]へは'0'が選ばれ*1
#以下、N[i-1]!=0の条件付き
# dp[0][j][i-1]からdp[1][j][i]へは'0'が選ばれ*1
# dp[0][j-1][i-1]からdp[1][j][i]へは'N[i-1]-1'までが選ばれ*(N[i-1]-1)

for i in range(1,L):
    for j in range(1,4):
        dp[1][j][i]+=dp[1][j-1][i-1]*9
        dp[1][j][i]+=dp[1][j][i-1]
        if int(N[i-1])>0:
            dp[1][j][i]+=dp[0][j][i-1]
            dp[1][j][i]+=dp[0][j-1][i-1]*(int(N[i-1])-1)
            

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

Submission status: Accepted

Solution code:
from functools import lru_cache

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

@lru_cache(None)
def dp(N, K):
  if N < 10:
    if K == 0:
      return 1
    if K == 1:
      return N
    return 0
  q, r = divmod(N, 10)
  ret = 0
  if K >= 1: # 下一桁が0でないときはKを1消化
    ret += dp(q, K-1) * r # 下一桁がr以下の時
    ret += dp(q-1, K-1) * (9-r) # 下一桁がrより上の時はq-1であれば成立
  ret += dp(q, K) # 下一桁が0のとき
  return ret

print(dp(N, K))

Submission status: Accepted

Solution code:
s=input()*2;n=len(s)/2
def f(i,t,k):
 if k>n-i:return 0
 a=max(t,int(s[i]));i+=1;
 if t:return f(i,9,k)+a*f(i,9,k-1)if k else 1
 else:return(f(i,9,k)+(a-1)*f(i,9,k-1)+f(i,0,k-1)if k else 1)if a else f(i,0,k)
print(f(0,0,int(input())))

Submission status: Accepted

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

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

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

ans = dp[n][K][0] + dp[n][K][1]

print(ans)

Submission status: Accepted

Solution code:
s=input();n=len(s)
def f(i,t,k):
 if k>n-i:return 0
 a=max(t,int(s[i]));i+=1;
 return(f(i,9,k)+(a-1)*f(i,9,k-1)+f(i,t,k-1)if k-1 else a+(n-i)*9)if a else f(i,t,k)
print(f(0,0,int(input())))

Submission status: Accepted

Solution code:
def comb(n, k):
  c = 1
  for i in range(k):
    c *= n-i
    c //= i+1
  return c

n = [int(i) for i in input()]
l = len(n)
k = int(input())
count = 0
for i in range(l):
  if n[i] > 0:
    # n[:i] 0 {1..9}*k 0*(l-i-1-k)
    count += 9 ** k * comb(l-i-1, k)
    # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
    if k >= 1:
      count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
    else:
      break
    # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
    k -= 1
  if i == l-1 and k == 0:
    count += 1
print(count)

Submission status: Accepted

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

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

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

for i in range(len(N)):
  n = int(N[i])
  for j in range(K+1):
    for ltn in range(2):
      for x in range(10 if ltn else n+1):
        if j + (x > 0) > K : continue
        dp[i+1][j + (x > 0)][ltn | (x < n)] += dp[i][j][ltn]

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

Submission status: Accepted

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

n = len(s)

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


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

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

Submission status: Accepted

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

count = len(N)

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

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

for i in range(count):
    for j in range(4):
        for k in range(2):
            nd = int(N[i])
            for d in range(10):
                ni = i + 1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

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

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

L=len(str(N))
ans=0
if L-1>=K:
    ans=cmb(L-1,K)*(9**K)

List=[]
for i in range(1,10):
    List.append(i*10**(L-1))

import sys
if K==1:
    for i in List:
        if i<=N:
            ans+=1
        else:
            print(ans)
            sys.exit()
    print(ans)
elif K==2:
    for i in List:
        for j in range(L-1):
            for k in range(1,10):
                T=i+k*10**j
                if T<=N:
                    ans+=1
                else:
                    print(ans)
                    sys.exit()
    print(ans)
elif K==3:
    for i in List:
        for j in range(L):
            for k in range(j+1,L-1):
                T=i+9*10**j+9*10**k
                if T<=N:
                    ans+=81
                else:
                    for l in range(1,10):
                        for m in range(1,10):
                            T=i+m*10**j+l*10**k
                            if T<=N:
                                ans+=1
                            else:
                                continue
    print(ans)
else:
    print(0)

Submission status: Accepted

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

def rec(N,K):
    if K==0:
        return 1#N以下の数で、0以外の数が０、すなわち残りの桁が全て０になるパターン

    if len(N)<K:
        return 0
    
    lsb=int(N[-1])

    if len(N)==1:
        return lsb
   
    return rec(N[:-1],K-1)*(lsb)+rec(str(int(N[:-1])-1),K-1)*(9-lsb)+rec(N[:-1],K)
    
print(rec(N,K))

Submission status: Accepted

Solution code:
# 解説放送

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

    dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    # dp[i][j][k]
    # i桁目まで決めてj個の非0を使って
    # k=0: そこまでの桁はSと一致
    # k=1: すでにS未満が確定

    for i, c in enumerate(S):  # 100
        for j in range(K + 1):  # 4
            for k in range(2):  # 2
                nd = int(c)
                for d in range(10):  # 10
                    ni, nj, nk = i + 1, j, k
                    if d != 0: nj += 1  # 次の桁の値dとして0以外を採用すると非0の個数njが増える
                    if nj > K: continue  # 非0の数字を使用してよい上限を超えており、加算対象ではない
                    if k == 0:  # そこまでSと一致しているとき
                        if d > nd: continue  # 次の桁の値dがS[i]を超えており、採用するとSを超えるため、加算対象ではない
                        if d < nd: nk = 1  # 次の桁の値dがs[i]を下回っており、採用すると未満が確定する
                    dp[ni][nj][nk] += dp[i][j][k]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=open(0)
k=int(k)
d=[1]+[0]*7
for n in map(int,n[:-1]):
  p=[0]*8
  for i in range(n):
    if i<1:
      for j in range(4):
        p[j+4]+=d[j]
    else:
      for j in range(3):
        p[j+5]+=d[j]
  for i in range(10):
    if i<1:
      for j in range(4):
        p[j+4]+=d[j+4]
    else:
      for j in range(3):
        p[j+5]+=d[j+4]
  if n<1:
    for i in range(4):
      p[i]+=d[i]
  else:
    for i in range(3):
      p[i+1]+=d[i]
  d=p
print(sum(d[k::4]))

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 1
    if N < 10:
        if K == 1: return N
        return 0
    q, r = divmod(N, 10)
    ret = 0
    ret += f(q, K)
    ret += f(q, K-1) * r
    ret += f(q-1, K-1) * (9-r)
    return ret

print(f(N, K))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = input().strip()
k = int(input())
l = len(n)

dp = [[[0] * (k+1) for _ in range(2)] for _ in range(l+1)]
dp[0][1][0] = 1
for i, s in enumerate(n, start=1):
    s = int(s)
    for j in range(10):
        if j == 0:
            if j < s:
                for x in range(k+1):
                    dp[i][0][x] += dp[i-1][0][x] + dp[i-1][1][x]
            elif j == s:
                for x in range(k+1):
                    for y in range(2):
                        dp[i][y][x] += dp[i-1][y][x]
        elif j < s:
            for x in range(k):
                dp[i][0][x+1] += dp[i-1][0][x] + dp[i-1][1][x]
        elif j == s:
            for x in range(k):
                for y in range(2):
                    dp[i][y][x+1] += dp[i-1][y][x]
        else:
            for x in range(k):
                dp[i][0][x+1] += dp[i-1][0][x]
print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Accepted

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

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

    ret = search(d + 1, k, isLess or int(N[d]) > 0)

    if k < K:
        if isLess:
            ret += search(d + 1, k + 1, True) * 9
        elif int(N[d]) > 0:
            ret += search(d + 1, k + 1, True) * (int(N[d]) - 1) + search(d + 1, k + 1, False)

    return ret

ans = search(0, 0, False)
print(ans)

Submission status: Accepted

Solution code:

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

def cmb(n, r):
    if r < 0 or r > n:
        return 0
    if r == 1:
        return n
    elif r == 2:
        return n * (n-1) // 2
    else:
        return n * (n-1) * (n-2) // (3 * 2) 

def rec(i, k, isSmaller):
    if i == N:
        if k == 0:
            return 1
        else:
            return 0
    
    if k == 0:
        return 1
    
    if isSmaller:
        return cmb(N-i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i+1, k, False)
        else:
            zero = rec(i+1, k, True)
            between = rec(i+1, k-1, True) * (int(S[i]) - 1)
            same = rec(i+1, k-1, False)
            return zero + between + same

print(rec(0, K, False))

Submission status: Accepted

Solution code:
import numpy as np

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

keta = len(S)

ans = 0
if keta < K:
    print(ans)
    exit()

dp = np.zeros((keta+2,4,2), dtype = int)
dp[0][0][0] = 1
for i in range(keta):
    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]

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

# 必要なだけforを回す
for i in range(2, 10 ** 6):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

# nCr n個から重複を許さずr個の組み合わせを選ぶ
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % MOD

def rec(i, k, isSmaller):
    if i == N:
        if k == 0:
            return 1
        else:
            return 0
    
    if k == 0:
        return 1
    
    if isSmaller:
        return cmb(N-i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i+1, k, False)
        else:
            zero = rec(i+1, k, True)
            between = rec(i+1, k-1, True) * (int(S[i]) - 1)
            same = rec(i+1, k-1, False)
            return zero + between + same

print(rec(0, K, False))