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:
# coding: utf-8


def solve(*args: str) -> str:
    N = list(map(int, '0' + (args[0])))
    k = int(args[1])

    d = len(N)-1
    F = [[0]*(k+1) for _ in range(d+1)]
    U = [[0]*(k+1) for _ in range(d+1)]

    U[0][0] = 1
    for i in range(1, d+1):
        for j in range(1, k+1):
            # set zero on i_th digit
            F[i][j-1] += F[i-1][j-1] + U[i-1][j-1]*(0 < N[i])
            U[i][j-1] += U[i-1][j-1]*(0 == N[i])

            # set non-zero on i_th digit
            F[i][j] += max(0, N[i]-1)*U[i-1][j-1] + 9*F[i-1][j-1]
            U[i][j] += U[i-1][j-1]*(0 < N[i])

    return str(sum(x[k] for x in F+U))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 無限 #####
# inf = float('inf')

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')

def main():
	S = input()
	S = S[:-1]
	N = len(S)

	K = inputInt()

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

	cnt = 1
	for i in range(N):
		for j in range(K+1):
			for k in range(2):
				targetN = int(S[i])
				for num in range(10):
					ni = i+1
					nj = j
					nk = k

					if num != 0:
						nj += 1
						if nj > K:
							continue

					if k == 0:
						if num > targetN:
							continue
						elif num == targetN:
							nk = 0
						else:
							nk = 1
					else:
						nk = 1

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

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

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    k = int(args[1])

    N = list(map(int, '0' + str(n)))
    d = len(str(n))
    F = [[0]*(k+1) for _ in range(d+1)]
    U = [[0]*(k+1) for _ in range(d+1)]

    U[0][0] = 1
    for i in range(1, d+1):
        for j in range(1, k+1):
            if 0 < N[i]:
                F[i][j-1] += F[i-1][j-1] + U[i-1][j-1]
                U[i][j] += U[i-1][j-1]
            else:
                F[i][j-1] += F[i-1][j-1]
                U[i][j-1] += U[i-1][j-1]
            F[i][j] += max(0, N[i]-1)*U[i-1][j-1] + 9*F[i-1][j-1]
    return str(sum([x[k] for x in F])+sum([x[k] for x in U]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
n = input()
k = int(input())
n_len = len(n)
dp0 = [[0]*k for i in range(n_len)]
dp1 = [[0]*k for i in range(n_len)]
for i in range(k):
    if i == 0:
        dp0[0][i]=int(n[0])-1
        dp1[0][i]=1
    else:
        dp0[0][i]=0
        dp1[0][i]=0

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

Submission status: Accepted

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

dp = [[[0, 0] for i in range(4)] for j in range(N+1)]
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):
                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[i+1][nj][nk] += dp[i][j][k]

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

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 a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if 0 != d:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if d < nd:
                        nc = 1
                    if d > nd:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

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 a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if 0 != d:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if nd > d:
                        nc = 1
                    if nd < d:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Submission status: Accepted

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

# dp[i][j][k]:問題の条件を満たす数の個数
# i桁目まで決定している。
# 非0の桁がすでにj個ある。
# k=0:i桁目までNと一致。k=1:すでにN以下であることが決まっている。

dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(len(N)+1)]
dp[0][0][0] = 1
for i in range(len(N)):
  n = int(N[i])
  for j in range(4):
    for k in range(2):
      for d in range(10): # d:i+1桁目の数字
        # ni,nj,nk:次の遷移先
        ni = i+1
        nj = j
        nk = k
        if d > 0:
          nj += 1
        if nj > K:
          continue
        if k == 0:
          if d > n:
            continue
          if d < n:
            nk = 1
        dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
def e(): exit()
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]

## dp1:top   dp2:under
dp1=[[0]*(k+2) for i in range(x)]
dp2=[[0]*(k+2) for i in range(x)]

dp1[0][0]=1
dp1[0][1]=0
dp2[0][0]=0
dp2[0][1]=0

cnt=0
for i in range(1,x):
    if l[i]>0:
        cnt+=1
    if cnt<=k:
        dp1[i][cnt]=1
for i in range(1,x):
    for j in range(k+1):
        if j==0:
            dp2[i][0]=1
        else:
            dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))+([dp1[i-1][j],0][l[i]==0])
print(dp1[-1][-2]+dp2[-1][-2])

Submission status: Accepted

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

dp = [[[1, 0], [0, 0], [0, 0], [0, 0]] for i in range(L)]
dp[0] = [[1, 0], [int(S[0])-1, 1], [0, 0], [0, 0]]

for l in range(1,L):
    s = int(S[l])
    if s == 0:
        for k in range(1,4):
            dp[l][k][1] += dp[l-1][k][1]
    else:
        for k in range(1,4):
            dp[l][k][1] += dp[l-1][k-1][1]
            dp[l][k][0] += dp[l-1][k][1]
    for k in range(1,4):
        dp[l][k][0] += dp[l-1][k-1][0]*9 + dp[l-1][k][0]
        dp[l][k][0] += dp[l-1][k-1][1]*max(0,s-1)

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

Submission status: Accepted

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

dp = [[[1, 0], [0, 0], [0, 0], [0, 0]] for i in range(L)]
dp[0] = [[1, 0], [int(S[0])-1, 1], [0, 0], [0, 0]]

for l in range(1,L):
    s = int(S[l])
    if s == 0:
        dp[l][1][1] += dp[l-1][1][1]
        dp[l][2][1] += dp[l-1][2][1]
        dp[l][3][1] += dp[l-1][3][1]
    else:
        dp[l][1][1] += dp[l-1][0][1]
        dp[l][2][1] += dp[l-1][1][1]
        dp[l][3][1] += dp[l-1][2][1]
        dp[l][1][0] += dp[l-1][1][1]
        dp[l][2][0] += dp[l-1][2][1]
        dp[l][3][0] += dp[l-1][3][1]

    dp[l][1][0] += dp[l-1][0][0]*9 + dp[l-1][1][0]
    dp[l][2][0] += dp[l-1][1][0]*9 + dp[l-1][2][0]
    dp[l][3][0] += dp[l-1][2][0]*9 + dp[l-1][3][0]
    dp[l][1][0] += dp[l-1][0][1]*max(0,s-1)
    dp[l][2][0] += dp[l-1][1][1]*max(0,s-1)
    dp[l][3][0] += dp[l-1][2][1]*max(0,s-1)

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

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
S = str(N)
'''
ans = 0
li = []
for i in range(1,N+1):
    if str(i).count('0') == len(str(i)) - K:
        ans += 1
        li.append(i)
print(ans)
print(li)
'''
L = len(S)

dp = [[[1, 0], [0, 0], [0, 0], [0, 0]] for i in range(L)]
dp[0] = [[1, 0], [int(S[0])-1, 1], [0, 0], [0, 0]]
#print(dp)
for l in range(1,L):
    s = int(S[l])
    if s == 0:
        dp[l][1][1] += dp[l-1][1][1]
        dp[l][2][1] += dp[l-1][2][1]
    else:
        dp[l][1][1] += dp[l-1][0][1]
        dp[l][2][1] += dp[l-1][1][1]
        dp[l][3][1] += dp[l-1][2][1]
        dp[l][1][0] += dp[l-1][1][1]
        dp[l][2][0] += dp[l-1][2][1]
        dp[l][3][0] += dp[l-1][3][1]

    dp[l][1][0] += dp[l-1][0][0]*9 + dp[l-1][1][0]
    dp[l][2][0] += dp[l-1][1][0]*9 + dp[l-1][2][0]
    dp[l][3][0] += dp[l-1][2][0]*9 + dp[l-1][3][0]
    dp[l][1][0] += dp[l-1][0][1]*max(0,s-1)
    dp[l][2][0] += dp[l-1][1][1]*max(0,s-1)
    dp[l][3][0] += dp[l-1][2][1]*max(0,s-1)

#print(dp)
print(sum(dp[L-1][K]))

Submission status: Accepted

Solution code:
from functools import lru_cache

def almost_everywhere_zero():
    N=int(input())
    K=int(input())
    print(f(N,K))
    
@lru_cache(None)
def f(n,k):
    if n<=10:
        if k==0:
            return 1
        if k==1:
            return n
        return 0
    div_n=n//10
    mod_n=n%10
    ans=f(div_n,k-1)*mod_n + f(div_n-1,k-1)*(9-mod_n) + f(div_n,k)
    return ans


almost_everywhere_zero()

Submission status: Accepted

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

KK = int(input())
dp = [[[0]*(5) for _ in range(2)] for _ in range(N+1)]
dp[0][0][0] = 1

for i, s in enumerate(K):
    a = ord(s)-48
    for j in range(4):
        for k in range(10):
            p = j+1 if k else j
            dp[i+1][1][p] += dp[i][1][j]
            if k<a:
                dp[i+1][1][p] += dp[i][0][j]

    for j in range(4):
        p = j+1 if a else j
        dp[i+1][0][p] += dp[i][0][j]

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

Submission status: Accepted

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

for i in range(1, l+1):
    m = int(n[i-1])
    for j in range(k+1):
        
        dp[i][1][j] += dp[i-1][1][j]*1  # 0
        if j - 1 >= 0:
            dp[i][1][j] += dp[i-1][1][j-1]*9  # 1〜9
            
        if m == 0:
            pass
        elif m >= 1:
            dp[i][1][j] += dp[i-1][0][j]
            if j - 1>= 0:
                dp[i][1][j] += dp[i-1][0][j-1]*(m-1)
        
        if m == 0:
            dp[i][0][j] += dp[i-1][0][j]
        else:
            if j - 1>= 0:
                dp[i][0][j] += dp[i-1][0][j-1]
        
print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()

N = list(map(int, input()))
K = int(input())

# dp[i][j][0] ... i + 1 digits, j non-zero digits, maybe ok
# dp[i][j][1] ... i + 1 digits, j non-zero digits, must be ok

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

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

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

Submission status: Accepted

Solution code:
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]

## dp1:top   dp2:under
dp1=[[0]*(k+2) for i in range(x)]
dp2=[[0]*(k+2) for i in range(x)]

dp1[0][0]=1
dp1[0][1]=0
dp2[0][0]=0
dp2[0][1]=0

cnt=0
for i in range(1,x):
    if l[i]>0:
        cnt+=1
    if cnt<=k:
        dp1[i][cnt]=1
for i in range(1,x):
    for j in range(k+1):
        if j==0:
            dp2[i][0]=1
        else:
            if l[i]==0: dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))
            else: dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))+(dp1[i-1][j])
print(dp1[-1][-2]+dp2[-1][-2])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = [int(c) for c in input()]
k = int(input())
dp0 = [1, n[0] - 1] + [0 for j in range(2, k + 1)]
dp1 = [0, 1] + [0 for j in range(2, k + 1)]
for i in range(2, len(n) + 1):
    for j in range(k, 0, -1):
        dp0[j] = (dp0[j - 1] * 9 + dp0[j] + dp1[j - 1] * max(n[i - 1] - 1, 0)
                  + dp1[j] * int(n[i-1] != 0))
    if n[i - 1] != 0:
        dp1 = [0] + dp1[:-1]
print(dp0[-1] + dp1[-1])

Submission status: Accepted

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

len_N = len(N)

dp = [[[0 for _ in range(K + 2)] for _ in range(2)] for _ in range(len_N + 1)]
dp[0][0][0] = 1 # position, is_less, num_of_zeros
for i in range(len_N):
    for j in range(2):
        for k in range(K + 1):
            lim = 9 if j else int(N[i])
            for d in range(lim + 1):
                if d != 0:
                    dp[i + 1][j or d < lim][k + 1] += dp[i][j][k]
                else:
                    dp[i + 1][j or d < lim][k] += dp[i][j][k]
ans = 0
for i in range(2):
    ans += dp[len_N][i][K]
print(ans)
# for d in dp:
#     print(d)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    S = input()  # 1以上S以下の整数
    n = len(S)   # n:整数Sの桁数
    K = int(input())

    # 桁DP
    # dp[i][j][k] := i桁目まで決めて
    #                j個の非ゼロを使って
    #                k:0なら、そこまでの桁はNと一致
    #                k:1なら、そこまでの桁ですでにN以下であることが確定
    #                したときの場合の数
    dp = [[[0 for _ in range(2)] for __ in range(4)] for ___ in range(n+1)]
    dp[0][0][0] = 1  # 何も決めていない状態で、非ゼロを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):
                    # 次の桁の値dを全部試す
                    ni = i + 1
                    nj = j
                    nk = k

                    if d != 0: nj += 1
                    if nj > K:
                        # 範囲を超えるなら
                        continue
                    if k == 0:
                        # 今の状態がNと一致しているなら
                        if d > nd:
                            # 次の桁が、今の桁の値より大きかったらダメ
                            continue
                        elif d < nd:
                            # 次の桁が、今の桁より小さかったら、「N以下」になることが確定する
                            nk = 1

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

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#E 復習復習
N = int(input())
K = int(input())
 
from functools import lru_cache
 
@lru_cache(None)
def f(n, K):
    if n <= 10:
        if K == 0:
            return 1
        if K == 1:
            return n
        return 0
    div_n = n//10
    mod_n = n%10
    ans = 0
#     if K >= 1:
    ans += f(div_n, K-1) * mod_n
    ans += f(div_n-1, K-1) * (9 - mod_n)
    ans += f(div_n, K)
    return ans
 
print(f(N, K))

Submission status: Accepted

Solution code:
#E 復習
N = int(input())
K = int(input())

from functools import lru_cache

@lru_cache(None)
def f(n, K):
    if n <= 10:
        if K == 0:
            return 1
        if K == 1:
            return n
        return 0
    div_n = n//10
    mod_n = n%10
    ans = 0
    if K >= 1:
        ans += f(div_n, K-1) * mod_n
        ans += f(div_n-1, K-1) * (9 - mod_n)
    ans += f(div_n, K)
    return ans

print(f(N, K))

Submission status: Accepted

Solution code:
#almost everywhere zero

n=input()
k=int(input())
dp_small=[[0 for i in range(4)] for j in range(101)]
dp_same=[[0 for i in range(4)] for j in range(101)]

#dp/smallすでに小さい
#dp_largeまだ小さいかどうかわからない
for i in range(101):
    dp_small[i][0]=1
dp_small[0][0]=0
dp_same[0][0]=1
for i in range(len(n)):
    a=int(n[i])
    #左からi+1番目の桁について考える
    if a!=0:
        dp_small[i+1][1]=dp_small[i][1]+9*dp_small[i][0]+(a-1)*dp_same[i][0]+dp_same[i][1]
        dp_small[i+1][2]=dp_small[i][2]+9*dp_small[i][1]+(a-1)*dp_same[i][1]+dp_same[i][2]
        dp_small[i+1][3]=dp_small[i][3]+9*dp_small[i][2]+(a-1)*dp_same[i][2]+dp_same[i][3]

        dp_same[i+1][1]=dp_same[i][0]
        dp_same[i+1][2]=dp_same[i][1]
        dp_same[i+1][3]=dp_same[i][2]       
        
        
        
        
    elif a==0:
        dp_small[i+1][1]=dp_small[i][1]+9*dp_small[i][0]
        dp_small[i+1][2]=dp_small[i][2]+9*dp_small[i][1]
        dp_small[i+1][3]=dp_small[i][3]+9*dp_small[i][2]

        dp_same[i+1][1]=dp_same[i][1]
        dp_same[i+1][2]=dp_same[i][2]
        dp_same[i+1][3]=dp_same[i][3]
        
L=len(n)
sums= dp_small[L][k]+dp_same[L][k]

print(sums)

Submission status: Accepted

Solution code:
import numpy as np
N = input()
K = int(input())
L = len(N)
dp0 = [[0]*(K+1) for i in range(L+1)]
dp1 = [[0]*(K+1) for i in range(L+1)]
dp0[0][0] = 1
for i in range(1,L+1):#i桁目
  c = int(N[i-1])
  for j in range(K+1):#k個0を使っているとする
    if j==0:
      if c>0:
        dp1[i][j] = dp1[i-1][j]+dp0[i-1][j]
        dp0[i][j] = 0
      else:
        dp1[i][j] = dp1[i-1][j]
        dp0[i][j] = dp0[i-1][j]
    else:
      if c>0:
        dp1[i][j] = dp0[i-1][j-1]*(c-1)+dp1[i-1][j-1]*9+dp1[i-1][j]+dp0[i-1][j]
        dp0[i][j] = dp0[i-1][j-1]
      else:
        dp1[i][j] = dp1[i-1][j-1]*9+dp1[i-1][j]
        dp0[i][j] = dp0[i-1][j]
print(dp0[-1][-1]+dp1[-1][-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    dp = [[0]*4 for _ in range(2)] # dp[lt][k] lt:less than, k:num of non-zero
    dp[0][0] = 1
    for a in input():
        a = int(a)
        ndp = [[0]*4 for _ in range(2)]
        for lt, k, d in product([0,1], range(4), range(10)):
            # less than
            if (not lt) and d > a: continue
            nlt = max(lt, d < a)
            # zero
            nk = k + (d>0)
            if nk > 3: continue
            # iterate
            ndp[nlt][nk] += dp[lt][k]
        dp = ndp

    k = int(input())
    print(dp[0][k] + dp[1][k])
resolve()

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 a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if 0 != d:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if nd > d:
                        nc = 1
                    if nd < d:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

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 a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if 0 != d:
                    nb += 1
                if k < nb:
                    break
                if 0 == nc:
                    if nd > d:
                        nc = 1
                    if nd < d:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

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 a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if 0 != d:
                    nb += 1
                if k < nb:
                    break
                if 0 == nc:
                    if nd > d:
                        nc = 1
                    if nd < d:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:

def main():
    ns = input()
    k = int(input())

    l = len(ns)

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

    for i in range(l):
        c = int(ns[i])

        dp_n = [[0, 0] for _ in range(k+1)]

        for j in range(k + 1):
            if c == 0:
                dp_n[j][0] += dp[j][0]
            else:
                dp_n[j][1] += dp[j][0]
                if j+1 <= k:
                    dp_n[j+1][1] += dp[j][0] * (c - 1)
                    dp_n[j+1][0] += dp[j][0]

            dp_n[j][1] += dp[j][1]
            if j+1 <= k:
                dp_n[j+1][1] += dp[j][1] * 9

        dp = dp_n

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


main()

Submission status: Accepted

Solution code:

def dyn(n,d00,d01,d02,d03,d10,d11,d12,d13):
    D00 = d00 + d10*int(n != 0)
    D10 = d10*int(n==0)
    D01 = d00*9 + d10*(n-1+int(n==0)) + d01 + d11*int(n!=0)
    D11 = d10*(int(n!=0)) + d11*(int(n==0))
    D02 = d01*9 + d11*(n-1+int(n==0)) + d02 + d12*int(n!=0)
    D12 = d11*(int(n!=0)) + d12*(int(n==0))
    D03 = d02*9 + d12*(n-1+int(n==0)) + d03 + d13*int(n!=0)
    D13 = d12*(int(n!=0)) + d13*(int(n==0))
    return D00,D01,D02,D03,D10,D11,D12,D13

N = str(input())
K = int(input())
S = len(N)
D00=0
D01=0
D02=0
D03=0
D10=1
D11=0
D12=0
D13=0

for i in range(S):
    [D00,D01,D02,D03,D10,D11,D12,D13] = dyn(int(N[i]),D00,D01,D02,D03,D10,D11,D12,D13)
    #print(int(N[i]),D00,D01,D02,D03,D10,D11,D12,D13)
if K == 1:
    print(D01+D11)
elif K==2:
    print(D02+D12)
else:
    print(D03+D13)

Submission status: Accepted

Solution code:
def dyn(n,d00,d01,d02,d03,d10,d11,d12,d13):
    D00 = d00 + d10*int(n != 0)
    D10 = d10*int(n==0)
    D01 = d00*9 + d10*(n-1+int(n==0)) + d01 + d11*int(n!=0)
    D11 = d10*(int(n!=0)) + d11*(int(n==0))
    D02 = d01*9 + d11*(n-1+int(n==0)) + d02 + d12*int(n!=0)
    D12 = d11*(int(n!=0)) + d12*(int(n==0))
    D03 = d02*9 + d12*(n-1+int(n==0)) + d03 + d13*int(n!=0)
    D13 = d12*(int(n!=0)) + d13*(int(n==0))
    return D00,D01,D02,D03,D10,D11,D12,D13

N = str(input())
K = int(input())
S = len(N)
D00=0
D01=0
D02=0
D03=0
D10=1
D11=0
D12=0
D13=0

for i in range(S):
    [D00,D01,D02,D03,D10,D11,D12,D13] = dyn(int(N[i]),D00,D01,D02,D03,D10,D11,D12,D13)

if K == 1:
    print(D01+D11)
elif K==2:
    print(D02+D12)
else:
    print(D03+D13)

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:
S = input()
K = int(input())

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

for i in range(1, length + 1):
    for j in range(2):
        for k in range(K + 1):
            os = int(S[i - 1])
            for x in range(10):
                ni = i
                nj = j
                nk = k
                if x != 0:
                    nk += 1
                if nk > K:
                    continue
                if j == 0:
                    if x > os:
                        continue
                    elif x < os:
                        nj = 1
                dp[ni][nj][nk] += dp[i - 1][j][k]

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

Submission status: Accepted

Solution code:
n = input()
m = len(n)
K = int(input())
#状態をもつ：i桁目まで見たときのj（その値は指定された値未満かどうか）において0でない数字がk個ある状態
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):
        #その値通りだった時、l=0だと0の数を増やせないのでi-1桁目でk個になってる個数を引き継ぐ
        #l!=0の場合にはまだ増やせるのでi-1桁目でk-1個になってる個数を引き継ぐ
        if k >= 1 and l != 0:
            dp[i][0][k] = dp[i-1][0][k-1]
        elif l == 0:
            dp[i][0][k] = dp[i-1][0][k]
        
        #base
        dp[i][1][k] = dp[i-1][1][k]

        #l!=0の時はi-1桁目でk個になってる個数を足すk=3 1000 -> 10002
        if l != 0:
            dp[i][1][k] += dp[i-1][0][k]

        #i-1桁目の個数から*9したものをたす(lがなんでも。どうせ未満だから)
        if k >= 1:
            dp[i][1][k] += 9 * dp[i-1][1][k-1]
            if l != 0:
                dp[i][1][k] += (l-1)*dp[i-1][0][k-1]
        

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

Submission status: Accepted

Solution code:
n = input()
m = len(n)
K = int(input())
#状態をもつ：i桁目まで見たときのj（その値は指定された値未満かどうか）において0でない数字がk個ある状態
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):
        
        #その値通りだった時、l=0だと0の数を増やせないのでi-1桁目でk個になってる個数を引き継ぐ
        if l == 0:
            dp[i][0][k] = dp[i-1][0][k]
        else:
            if k >= 1:
                #l!=0の場合にはまだ増やせるのでi-1桁目でk-1個になってる個数を引き継ぐ
                dp[i][0][k] = dp[i-1][0][k-1]
        

        dp[i][1][k] += dp[i-1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i-1][0][k]
        if k >= 1:
            dp[i][1][k] += 9*dp[i-1][1][k-1]
            if l != 0:
                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:
n = input()
m = len(n)
K = int(input())
#状態をもつ：i桁目まで見たときのj（その値は指定された値未満かどうか）において0でない数字がk個ある状態
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):
        
        #その値通りだった時、l=0だと0の数を増やせないので
        if l == 0:
            dp[i][0][k] = dp[i-1][0][k]
        else:
            if k >= 1:
                dp[i][0][k] += dp[i-1][0][k-1]
        

        dp[i][1][k] += dp[i-1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i-1][0][k]
        if k >= 1:
            dp[i][1][k] += 9*dp[i-1][1][k-1]
            if l != 0:
                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:
n = input()
m = len(n)
K = int(input())
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):
        
        if l == 0:
            dp[i][0][k] += dp[i-1][0][k]
        else:
            if k >= 1:
                dp[i][0][k] += dp[i-1][0][k-1]
        

        dp[i][1][k] += dp[i-1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i-1][0][k]
        if k >= 1:
            dp[i][1][k] += 9*dp[i-1][1][k-1]
            if l != 0:
                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
read = sys.stdin.read
n, k = map(int, read().split())


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


def solve(n, k):
    if k == 0:
        return 1
    digit = len(str(n))
    res = 0
    if digit > k:
        res += count(digit - 1, k) * (9 ** k)
    pow10 = 10 ** (digit - 1)
    d, mod = n // pow10, n % pow10
    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(digit, k):
    if digit < k:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return digit
    elif k == 2:
        return digit * (digit - 1) // 2
    else:
        return digit * (digit - 1) * (digit - 2) // 6


def solve(n, k):

    if k == 0:
        return 1
    digit = len(str(n))
    res = 0
    if digit > k:
        res += count(digit - 1, k) * (9 ** k)
    pow10 = 10 ** (digit - 1)
    d, mod = n // pow10, n % pow10
    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())
L = len(N)
dp0 = [[0]*(K+1) for i in range(L+1)]
dp1 = [[0]*(K+1) for i in range(L+1)]
dp0[0][0] = 1
for i in range(1,L+1):
  c = int(N[i-1])
  for j in range(K+1):
    if j==0:
      if c>0:
        dp1[i][j] = dp1[i-1][j]+dp0[i-1][j]
        dp0[i][j] = 0
      else:
        dp1[i][j] = dp1[i-1][j]
        dp0[i][j] = dp0[i-1][j]
    else:
      if c>0:
        dp1[i][j] = dp0[i-1][j-1]*(c-1)+dp1[i-1][j-1]*9+dp1[i-1][j]+dp0[i-1][j]
        dp0[i][j] = dp0[i-1][j-1]
      else:
        dp1[i][j] = dp1[i-1][j-1]*9+dp1[i-1][j]
        dp0[i][j] = dp0[i-1][j]
print(dp0[-1][-1]+dp1[-1][-1])