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:
import sys


def resolve(in_):
    N = next(in_).strip()
    K = int(next(in_))

    # exact
    dp0 = [[0] * (K + 1) for _ in range(len(N) + 1)]
    dp0[0][0] = 1
    # smaller
    dp1 = [[0] * (K + 1) for _ in range(len(N) + 1)]

    ord_zero = ord('0')
    for i, s in enumerate(map(lambda s: s - ord_zero, N)):
        for j in range(K + 1):
            dp1[i + 1][j] += dp1[i][j]
            if s > 0:
                dp1[i + 1][j] += dp0[i][j]
            else:
                dp0[i + 1][j] += dp0[i][j]
            if j < K:
                # smaller -> smaller
                dp1[i + 1][j + 1] += dp1[i][j] * 9
                # exact -> smaller
                dp1[i + 1][j + 1] += dp0[i][j] * max(0, (s - 1))
                # exact -> exact
                if s > 0:
                    dp0[i + 1][j + 1] += dp0[i][j]

    return dp0[len(N)][K] + dp1[len(N)][K]


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

    # dp[i][j][smaller]
    # i桁目まで見たときに0以外の数字をｊ個使用し、条件を満たす個数
    # smaller:
    # 0:i桁目まで見たときに一致している(次の桁は余裕が無い)
    # 1:次の桁は余裕がある

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

    for i in range(N):
        for j in range(4):
            for smaller in range(2):
                now = int(S[i])
                for d in range(10):
                    ni = i+1
                    nj = j
                    n_smaller = smaller
                    if d != 0:
                        nj += 1
                    if nj > K:
                        continue
                    if smaller == 0:
                        if d > now: # 値を超えている
                            continue
                        if d < now: # 次の桁は余裕がある
                            n_smaller = 1
                    dp[ni][nj][n_smaller] += dp[i][j][smaller]
    ans = dp[N][K][0] + dp[N][K][1]
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n=RD()
	k=II()

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

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

	for i in range(len(n)):
		now=int(n[i])
		for j in range(k+1):
			#print(i,j,now)
			dp[i+1][j+(now!=0)][0]+=dp[i][j][0]
			dp[i+1][j][1]+=dp[i][j][1]+dp[i][j][0]*(now!=0)
			dp[i+1][j+1][1]+=dp[i][j][1]*9+dp[i][j][0]*(now-1 if now>0 else 0)
		#print(dp)
	print(dp[len(n)][k][0]+dp[len(n)][k][1])

















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import numpy as np

N = list(map(int, input()))
K = int(input())
l = len(N)
if l < K:
    print(0)
    exit()

# dp[d][k] := d 桁目まで見て 0 でない数字が k 個ある場合の数
dp_small = np.zeros((l+1, K+1), dtype=np.int64)
dp_large = np.zeros((l+1, K+1), dtype=np.int64)
dp_large[0, 0] = 1
for d, digit in enumerate(N, 1):
    for k in range(K+1):
        # 0 を配置する
        dp_small[d, k] += dp_small[d-1, k]
        if digit != 0:
            dp_small[d, k] += dp_large[d-1, k]
            dp_large[d, k] = 0
        else:
            dp_large[d, k] = dp_large[d-1, k]
        if k!=0:
            # 0 以外を配置する
            dp_small[d, k] += dp_small[d-1, k-1] * 9
            if digit >= 1:
                dp_small[d, k] += dp_large[d-1, k-1] * (digit-1)
                dp_large[d, k] += dp_large[d-1, k-1]
print(dp_small[l, K] + dp_large[l, K])

Submission status: Accepted

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

ans = 0
if k == 1:
    ans = n[0] + (l - 1) * 9
elif k == 2:
    if l == 1:
        ans = 0
    else:
        for i in range(l - 1):
            p = True
            for j in range(i + 1, l):
                if i == 0 and p:
                    ans += (n[i] - 1) * 9 + n[j]
                elif i == 0:
                    ans += n[i] * 9
                else:
                    ans += 9 * 9
                if n[j] != 0:
                    p = False
else:
    if l <= 2:
        ans = 0
    else:
        for i in range(l - 2):
            p1 = True
            for j in range(i + 1, l - 1):
                p2 = True
                for k in range(j + 1, l):
                    if i == 0 and p1 and p2:
                        ans += (n[i] - 1) * 9 * 9
                        ans += (n[j] - 1) * 9 + n[k] if n[j] != 0 else 0
                    elif i == 0 and p1 and not p2:
                        ans += (n[i] - 1) * 9 * 9 + n[j] * 9
                    elif i == 0 and not p1:
                        ans += n[i] * 9 * 9
                    else:
                        ans += 9 * 9 * 9
                    if n[k] != 0:
                        p2 = False
                if n[j] != 0:
                    p1 = False
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

dp = [[[0]*2 for _ in range(K+1)] for _ in range(length+1)]
dp[0][0][1] = 1
for i in range(length):
    n = int(N[i])
    for k in range(K+1):
        if k==K:
            dp[i+1][k][0]+=dp[i][k][0]
            if n==0:
                dp[i+1][k][1]+=dp[i][k][1]
            else:
                dp[i+1][k][0]+=dp[i][k][1]
            continue
        for j in range(10):
            if j==0:
                if n==0:
                    dp[i+1][k][0]+=dp[i][k][0]
                    dp[i+1][k][1]+=dp[i][k][1]
                else:
                    dp[i+1][k][0]+=dp[i][k][0]+dp[i][k][1]
            elif j==n:
                dp[i+1][k+1][1]+=dp[i][k][1]
                dp[i+1][k+1][0]+=dp[i][k][0]
            elif j<n:
                dp[i+1][k+1][0]+=dp[i][k][0]+dp[i][k][1]
            else:
                dp[i+1][k+1][0]+=dp[i][k][0]
print(sum(dp[-1][K]))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = input()
n = len(s)
K = inp()
dp = [[[0 for i in range(5)] for j in range(2)] for k in range(n+1)]
# dp[i][j][k] j:0 kaku j:1 mikaku , k:kosuu
dp[0][1][0] = 1
for i,x in enumerate(s):
    x = int(x)
    for k in range(4):
        dp[i+1][0][k] += dp[i][0][k]
        dp[i+1][0][k+1] += dp[i][0][k]*9 + dp[i][1][k]*max(0,(x-1))

        if x != 0:
            dp[i+1][0][k] += dp[i][1][k]
            dp[i+1][1][k+1] = dp[i][1][k]
            if k == 0: dp[i+1][1][k] = 0
        else:
            dp[i+1][1][k] = dp[i][1][k] 
        for j in range(2):
            dp[i+1][j][k] %= mod

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

Submission status: Accepted

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

dp = [[[0,0] for _ in range(K+1)] for _ in range(L+1)]
dp[0][0][0] = 1
for i,c in enumerate(S):
    c = int(c)
    for k in reversed(range(K+1)):
        for d in range(10):
            nk = k + (d>0)
            if nk > K: continue
            dp[i+1][nk][1] += dp[i][k][1]
            if d > c: continue
            less = int(d < c)
            dp[i+1][nk][less] += dp[i][k][0]
print(sum(dp[-1][-1]))

Submission status: Accepted

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

def k2(l, n):
    ans = 81 * (l - 1) * (l - 2) // 2
    ans += (int(n[0]) - 1) * 9 * (l - 1)
    for i, s in enumerate(n[1:]):
        if s == "0":
            continue
        ans += int(s)
        ans += max((l - i - 2), 0) * 9
        break
    return ans

if k == 1:
    ans = (l - 1) * 9 + int(n[0])
elif k == 2:
    if l == 1:
        print(0)
        exit()
    ans = k2(l, n)
else:
    if l < 3:
        print(0)
        exit()
    ans = 9 ** 3 * (l - 1) * (l - 2) * (l - 3) // 6
    ans += (int(n[0]) - 1) * 81 * (l - 1) * (l - 2) // 2
    n = n[1:]
    n = str(int(n))
    ans += k2(len(n), n)
print(ans)

Submission status: Accepted

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

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

for i, s in enumerate(S):
    nd = int(s)
    for j in range(K+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 > K:
                    continue
                if nk == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk += 1
                dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

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

dp = [ [ [0]*2 for _ in range(4) ] for _ in range(L+1) ]
dp[0][0][0] = 1
for i in range(L):
  for j in range(K+1):
    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]

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

Submission status: Accepted

Solution code:
def calc(a,D,K):
  if K==1:
    return a+(D-1)*9
  elif K==2:
    return (a-1)*(D-1)*9 + (D-1)*(D-2)/2*81
  else:
    return (a-1)*(D-1)*(D-2)/2*81 + (D-1)*(D-2)*(D-3)/6*729

N=str(input())
K=int(input())
D = len(N)
score=0
for i,a in enumerate(N):	
  if a!="0":
    score+=calc(int(a),D-i,K)
    K-=1
  if K==0:
    break
print(int(score))

Submission status: Accepted

Solution code:
def resolve():
    N = list(input())
    lenN = len(N)
    K = int(input())
    dp = [[[None, None] for _ in range(K+1)] for __ in range(lenN)]

    def rec(i, k, smaller):
        if k==0:
            return 1
        if i>=lenN:
            return 0
        
        if dp[i][k][int(smaller)] is not None:
            return dp[i][k][int(smaller)]
        
        ret = 0
        if smaller:
            ret += rec(i+1, k, True)
            ret += rec(i+1, k-1, True) * 9
        else:
            if N[i] == "0":
                ret += rec(i+1, k, False)
            else:
                ret += rec(i+1, k, True) # 次も0を選ぶ
                ret += rec(i+1, k-1, True) * (int(N[i]) - 1) # 0 < ?? < N[i]
                ret += rec(i+1, k-1, False) # N[i]を選ぶ、真にsmallerとは限らないのでまだFalse
        
        dp[i][k][int(smaller)] = ret
        return ret

    print(rec(0, K, False))
    
    
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n = int(input())
K = int(input())

def make_list(n):
    N = []
    while(n>0):
        N.append(n%10)
        n = n //10
    N.reverse()
    return N

N = make_list(n)
m = len(N)
dp = [[[ 0 for k in range(K+1)] for j in range(2)] for i in range(m)]  
#dp[i][j][k]:上からi桁目で、j=0:nのi桁目までと等しくない,j=1:等しい、0でない数字がk個であるものの個数
dp[0][0][0] =  1 #x = 0
dp[0][0][1] = N[0] - 1 #0 < x < N[0]
dp[0][1][0] = 0
dp[0][1][1] = 1 #x = N[0]

for i in range(1,m):
    dp[i][0][0] = 1 #i桁目まで全部0
    #dp[i][1][0] = 0:最上位が0はありえない
    for k in range(1,K+1):
        if N[i] == 0:
            dp[i][0][k] = dp[i-1][0][k-1] * 9 + dp[i-1][0][k]
            dp[i][1][k] = dp[i-1][1][k]
        else:
            dp[i][0][k] = dp[i-1][0][k-1] * 9 + dp[i-1][0][k] + dp[i-1][1][k] + dp[i-1][1][k-1] * (N[i] - 1)
            dp[i][1][k] = dp[i-1][1][k-1]
#print(dp)
print(dp[m-1][1][K] + dp[m-1][0][K])

Submission status: Accepted

Solution code:
N = list(map(int, 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 j in range(K + 1):
        for is_smaller in range(2):
            for l in range(10):
                if not is_smaller and l > N[i] or l != 0 and j + 1 > K:
                    continue
                i_ = i + 1
                j_ = j
                is_smaller_ = is_smaller

                if l != 0:
                    j_ += 1

                if not is_smaller and l < N[i]:
                    is_smaller_ = 1
                dp[i_][j_][is_smaller_] += dp[i][j][is_smaller]
print(dp[len(N)][K][0] + dp[len(N)][K][1])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = input()
    K = I()

    dp1 = [[0] * len(N) for _ in range(K + 2)] #未確定
    dp2 = [[0] * len(N) for _ in range(K + 2)] #確定

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

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

n_self = int(len(N) - N.count("0") == K)
print(dp[-1][-1][-1] + n_self)

Submission status: Accepted

Solution code:
S = list(input())
K = int(input())
N = len(S)
dp = [[[0] * 2 for i in range(4)] for i in range(105)]
#print(dp)
dp[0][0][0] = 1
for i in range(N):
    nd = int(S[i])
    for j in range(4):
        for k in range(2):
            for d in range(10):
                ni = i+1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
#print(dp)
print(dp[N][K][0] + dp[N][K][1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10


def C(n, r):
	if n < r:
		return 0
	else:
		return factorial(n)//factorial(n-r)//factorial(r)

N = input()
K = INT()

n = len(N)

ans = 0
if K <= n-N.count("0"):
	ans += 1

for i in range(n):
	if N[i] != "0" and 0 < K:
		ans += (int(N[i])-1) * 9**(K-1) * C(n-i-1, K-1) + C(n-i-1, K) * 9**K
		K -= 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

m = len(s)
dp = np.zeros((m+1, 2, k+2), dtype=np.int64)
dp[0][1][0] = 1
for cs in range(m):
    cn = int(s[cs])
    for ck in range(k+2):
        if ck == k+1:
            nk = ck
        else:
            nk = ck + 1
        dp[cs+1][0][nk] += 9 * dp[cs][0][ck]
        dp[cs+1][0][ck] += dp[cs][0][ck]

        if cn == 0:
            dp[cs+1][1][ck] += dp[cs][1][ck]
        else:
            dp[cs+1][1][nk] += dp[cs][1][ck]
            dp[cs+1][0][nk] += (cn - 1) * dp[cs][1][ck]
            dp[cs+1][0][ck] += dp[cs][1][ck]
print(dp[m][0][k] + dp[m][1][k] )

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

    ans = 0
    # 最上位K桁が0の場合
    # l-K_C_K * 9^K
    if K == 1:
        ans += (l-1) * 9
    elif K == 2:
        ans += (l-1) * (l-2) * 81 // 2
    else:
        ans += (l-1) * (l-2) * (l-3) * 729 // 6

    if K == 1:
        # 最上位の数以外0
        ans += int(N[0])
    elif K == 2:
        # 最上位1桁が0ではなく,残りl-1桁中1桁だけ0以外（Nより大きくならないように注意）
        if l >= 2:
            # ans += int(N[0]) * (l-1) * 9 - (9 - int(N[1]))
            for a in range(1,int(N[0])+1):
                for b in range(l-1):
                    for p in range(1,10):
                        tmp = a * 10**(l-1) + p * 10**b
                        if tmp <= int(N):
                            ans += 1
    else:
        # 最上位1桁が0ではなく,残りl-1桁中2桁だけ0以外（Nより大きくならないように注意）
        if l >= 3:
            NN = int(N)
            N0 = int(N[0])
            L = 10**(l-1)

            ans += (N0-1) * (l-1) * (l-2) * 81 // 2

            for p in range(1,10):
                for q in range(1,10):
                    for b in range(l-1):
                        for c in range(b+1,l-1):
                            tmp = N0 * L + p * 10**b + q * 10**c
                            if tmp <= NN:
                                ans += 1
                            else:
                                break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

dp1=[0]*(k+1)
dp2=[0]*(k+1)
dp1[0]=1

for x in map(int,str(n)):
    for j in range(k,-1,-1):
        if j>0:
            dp2[j]+=dp2[j-1]*9
            if x!=0:
                dp2[j]+=dp1[j-1]*(x-1)+dp1[j]
                dp1[j]=dp1[j-1]
            #print(dp1)
            #print(dp2)
        else:
            dp2[j]=1
            dp1[j]=0
print(dp1[k]+dp2[k])

Submission status: Accepted

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

if len(N) < K:
  print(0)
  exit()

ans = [1, int(N[-1]), 0, 0];
nine = [1, 9, 81, 729]

def combination(N,K):
  if N < K:
    return 0
  elif K == 0:
    return 1
  elif K == 1:
    return N
  elif K == 2:
    return N*(N-1)//2
  else:
    return N*(N-1)*(N-2)//6

for k in range(1, len(N)):
  if int(N[-k-1]) > 0:
    a = [1, 0, 0, 0]
    for j in range(1, K+1):
      a[j] += nine[j]*combination(k, j)
      a[j] += (int(N[-k-1])-1)*combination(k, j-1)*nine[j-1] + ans[j-1]
    ans = a
print(ans[K])

Submission status: Accepted

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

if len(N) < K:
  print(0)
  exit()

ans = [1, int(N[-1]), 0, 0];

def combination(N,K):
  if N < K:
    return 0
  else:
    p = 1
    for k in range(K):
      p *= N
      N -= 1
    for k in range(1, K+1):
      p //= k
    return p

for k in range(1, len(N)):
  if int(N[-k-1]) > 0:
    a = [1, 0, 0, 0]
    for j in range(1, K+1):
      a[j] += (9**(j))*combination(k, j)
      a[j] += (int(N[-k-1])-1)*combination(k, j-1)*(9**(j-1)) + ans[j-1]
    ans = a
print(ans[K])

Submission status: Accepted

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

if len(N) < K:
  print(0)
  exit()

keta = []
for k in range(len(N)):
  keta.append(int(N[-k-1]))
ans = [1, keta[0], 0, 0];

def combination(N,K):
  if N < K:
    return 0
  else:
    p = 1
    for k in range(K):
      p *= N
      N -= 1
    for k in range(1, K+1):
      p //= k
    return p
for k in range(1, len(N)-1):
  if keta[k] > 0:
    a = [1, 0, 0, 0]
    for j in range(1, 4):
      a[j] += (9**(j))*combination(k, j)
      a[j] += (keta[k]-1)*combination(k, j-1)*(9**(j-1)) + ans[j-1]
    ans = [] + a
answer = (9**(K))*combination(len(N)-1, K)
answer += (keta[-1]-1)*(9**(K-1))*combination(len(N)-1, K-1)
answer += ans[K-1]
print(answer)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc154/tasks/abc154_e


def digit(N, M):
    """
    :param N: 0 <= n <= N の整数 (※ 下限が 1 の場合は返り値を -= 1 等する)
    :param M: 状態数（例: 0<= (0の個数) <= M）

    dp[0][i][*]: 上からi桁目までが N と一致
    dp[1][i][*]: 上からi桁目までで N である事が確定
    dp[*][*][j]: 状態 j の個数（今回は j = (0 の個数) ）
    """
    def f(j,k):
        """状態 j からの繊維。 i+1 桁目の数( = j)に依存"""
        return min2(j + (k != 0), M - 1)

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

    dp[0][0][0] = 1
    for i in range(L):
        for j in range(M):
            for k in range(10):
                if k < N[i]:
                    dp[1][i+1][f(j, k)] += dp[0][i][j] + dp[1][i][j]
                elif k == N[i]:
                    dp[0][i+1][f(j, k)] += dp[0][i][j]
                    dp[1][i+1][f(j, k)] += dp[1][i][j]
                else:
                    dp[1][i+1][f(j, k)] += dp[1][i][j]

    return dp[0][L][K] + dp[1][L][K]

##########################################################################################

N = list(map(int, input().strip()))     # 整数を桁毎のリストとして読み込む
K = int(input())
M = K + 2                               # 状態数

def min2(x,y):
    return x if x < y else y

print(digit(N, M))

Submission status: Accepted

Solution code:
N = list(map(int, input()))     # 整数を桁毎のリストとして読み込む
L = len(N)
K = int(input())
D = K + 2                       # 状態数
dp = [[[0] * D for i in range(L + 1)] for j in range(2)]

def min2(x,y):
    return x if x < y else y

"""
dp[0][i][*]: 上からi桁目までが N と一致
dp[1][i][*]: 上からi桁目までで N である事が確定
dp[*][*][j]: 0 でない数字の個数が j 個
"""
dp[0][0][0] = 1
for i in range(L):
    for j in range(D):
        for k in range(10):
            if k < N[i]:
                dp[1][i+1][min2(j + (k!=0), D-1)] += dp[0][i][j] + dp[1][i][j]
            elif k == N[i]:
                dp[0][i+1][min2(j + (k!=0), D-1)] += dp[0][i][j]
                dp[1][i+1][min2(j + (k!=0), D-1)] += dp[1][i][j]
            else:
                dp[1][i+1][min2(j + (k!=0), D-1)] += dp[1][i][j]

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

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def fn(pos,res,k):
    if pos==n:return (k==0)
    ans=0
    if (pos,res,k) in dp:return dp[pos,res,k]
    cur=ord(s[pos])-48
    if res:
        for d in range(cur+1):
            if d==0:ans+=fn(pos+1,d==cur,k)
            elif d!=0 and k>0:ans+=fn(pos+1,d==cur,k-1)
    else:
        for d in range(10):
            if d == 0:ans += fn(pos + 1,0, k)
            elif d != 0 and k > 0:ans += fn(pos + 1,0, k - 1)
    dp[pos,res,k]=ans
    return ans

#a,b=map(int,stdin.readline().split())
s=input()
n=len(s)
k1=int(stdin.readline())
dp={}
ans=0
for d in range(10):
    if d+48<=ord(s[0]):
        ans+=fn(1,(d==ord(s[0])-48),(k1-(d!=0)))
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = input()
    non_zero = int(input())
    length = len(n)
    dp = [[[0, 0] for _ in range(non_zero + 1)] for _ in range(length + 1)]
    dp[0][0][0] = 1
    for i in range(length):
        for j in range(non_zero + 1):
            for k in range(2):
                now_digit = int(n[i])
                for next_d in range(10):
                    new_i = i + 1
                    new_j = j
                    new_k = k
                    if next_d > 0:
                        new_j += 1
                    if new_j > non_zero:
                        continue
                    if k == 0:
                        if next_d > now_digit:
                            continue
                        elif next_d < now_digit:
                            new_k = 1
                    dp[new_i][new_j][new_k] += dp[i][j][k]
    print(sum(dp[length][non_zero]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
S = str(N)
L = len(S)
# dp0 N未満であることが未確定
# dp1 N未満であることが確定
# [上から何桁][0以外を選んだ回数]
dp0 = [[0 for _ in range(5)] for _ in range(L+1)]
dp1 = [[0 for _ in range(5)] for _ in range(L+1)]
dp0[0][0] = 1
dp0[0][1] = 0
for i in range(L):
    D = int(S[i])
    for j in range(4):
        if D > 0:
            # 0を選ぶ
            dp1[i+1][j] += dp1[i][j] + dp0[i][j]
            # 1~9を選ぶ
            dp0[i+1][j+1] += dp0[i][j]
            dp1[i+1][j+1] += dp1[i][j]*9 + dp0[i][j]*(D-1)
        else:
            # 0を選ぶ
            dp0[i+1][j] += dp0[i][j]
            dp1[i+1][j] += dp1[i][j]
            # 1~9を選ぶ
            dp1[i+1][j+1] += dp1[i][j]*9
print(dp0[L][K]+dp1[L][K])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
ln = len(n) + 1

dp=[[[0]* (ln) for _ in range(2)] for i in range(ln)]
dp[0][0][0] = 1
for i in range(len(n)):
  for smaller in range(2):
    x = int(n[i])
    t = 9 if smaller else x
    for j in range(t+1):
      for knum in range(ln-1):
        if j == 0:
          dp[i+1][int(smaller or j < x)][knum] += dp[i][smaller][knum]
        else:
          dp[i+1][int(smaller or j < x)][knum+1] += dp[i][smaller][knum]
try:
  print(dp[-1][0][k] + dp[-1][1][k])
except:
  print(0)

Submission status: Accepted

Solution code:
def solve():
    s = [int(x) for x in input()]
    n = len(s)
    m = int(input())
    dp = [[[0] * 5 for _ in range(2)] for _ in range(n + 1)]
    dp[0][0][0] = 1

    for i in range(n):
        for k in range(m + 1):
            dp[i + 1][1][k + 1] += dp[i][1][k] * 9  # add 1-9
            dp[i + 1][1][k] += dp[i][1][k]  # add 0
            if s[i] > 0:
                dp[i + 1][1][k + 1] += dp[i][0][k] * (s[i] - 1)  # add lower s[i]
                dp[i + 1][1][k] += dp[i][0][k]  # add 0
                dp[i + 1][0][k + 1] += dp[i][0][k]  # add s[i]
            else:
                dp[i + 1][0][k] += dp[i][0][k]  # add s[i] = 0
    print(dp[n][0][m] + dp[n][1][m])


solve()

Submission status: Accepted

Solution code:
# 桁DP練習
# 「0以外の値をkより多く使ったか」でとくに枝切りしてない
# ループでどうしてもかけない...

from sys import setrecursionlimit

setrecursionlimit(10**7)

n = input()
k = int(input())
dp = {}


def rec(i, smaller, count):
    if (i, smaller, count) in dp:
        return dp[(i, smaller, count)]
    if i == len(n):
        if count == k:
            return 1
        else:
            return 0
    limit = 10
    if not smaller:
        limit = int(n[i]) + 1
    ret = 0
    for j in range(limit):
        if smaller or j < int(n[i]):
            if j == 0:
                ret += rec(i + 1, True, count)
            else:
                ret += rec(i + 1, True, count + 1)
        else:
            if j == 0:
                ret += rec(i + 1, False, count)
            else:
                ret += rec(i + 1, False, count + 1)
    dp[(i, smaller, count)] = ret
    return ret


print(rec(0, False, 0))

Submission status: Accepted

Solution code:
def f(N,K):
    n=len(str(N))
    if n==1:
        if K==1:
            return N
        else:
            return 0
    elif n==2:
        if K==1:
            return 9+N//10
        elif K==2:
            return N-9-N//10
        else:
            return 0
    elif n==3:
        if K==1:
            return 18+N//100
        elif K==2:
            return 81+18*((N//100)-1)+f(N%100,1)
        else:
            return 81*((N//100)-1)+f(N%100,2)
    else:
        if K==1:
            return 9*(n-1)+N//(10**(n-1))
        elif K==2:
            return 81*(n-1)*(n-2)/2+9*(n-1)*((N//((10**(n-1))))-1)+f(N%(10**(n-1)),1)
        else:
            return 243*(n**3-6*(n**2)+11*n-6)/2+81*(n-1)*(n-2)*((N//(10**(n-1)))-1)/2+f(N%(10**(n-1)),2)
N=int(input())
K=int(input())
print(int(f(N,K)))

Submission status: Accepted

Solution code:
from math import factorial
from itertools import product

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

# 0でない数字がちょうどK個でK桁のものを数える
product_K = product(['1', '2', '3', '4', '5', '6', '7', '8', '9'], repeat=K)
product_K = [int(''.join(x)) for x in product_K]
ans = len([x for x in product_K if x <= N])

if m > K:
    # K+1桁からlen(N)-1桁までを数える
    for i in range(1, m-K):
        ans += 9**K * factorial(i+K-1)//factorial(i)//factorial(K-1)
    
    # Nと同じ桁数で条件を満たすものを数える
    zero_n = m-K
    non_zero_n = K
    for i in range(m):
        l = int(S[i])
        if l == 0:
            zero_n -= 1
            continue
        if i > 0 and zero_n > 0:
            ans += 9**non_zero_n\
                * factorial(zero_n-1 + non_zero_n)\
                //factorial(zero_n-1)\
                //factorial(non_zero_n)
        non_zero_n -= 1
        ans += len([x for x in range(1, l)])\
                * 9**non_zero_n\
                * factorial(zero_n + non_zero_n)\
                //factorial(zero_n)\
                //factorial(non_zero_n)
        
        if non_zero_n <= 0:
            ans += 1
            break
print(ans)