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
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    list_N = list(map(int,list(input())))
    len_N = len(list_N)
    list_N = [0] + list_N

    K = II()
    dp0 = []
    dp1 = []
    for i in range(len_N+1):
        dp0.append([0]*(K+1))
        dp1.append([0]*(K+1))
    for i in range(1,len_N+1):
        dp0[i][0] = 1
    dp0[1][1] = max(list_N[1]-1,0)
    dp1[1][1] = 1
    for i in range(2,len_N+1):
        dp1[i][0] = dp1[i-1][0]
        for j in range(1,K+1):
            num = list_N[i]
            if num > 0:
                dp0[i][j] = dp0[i-1][j-1] * 9 + dp0[i-1][j] + dp1[i-1][j-1] * (num-1) + dp1[i-1][j]
                dp1[i][j] = dp1[i-1][j-1]
            else:
                dp0[i][j] = dp0[i-1][j-1] * 9 + dp0[i-1][j]
                dp1[i][j] = dp1[i-1][j]
                
    print(dp0[len_N][K]+dp1[len_N][K])
    dbg(dp0[len_N][K],dp1[len_N][K])






if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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 == 0:
      return 1
    elif k == 1:
      return n
    else:
      return 0
  a, b = divmod(n, 10)
  return f(a, k) + f(a, k-1) * b + f(a-1, k-1) * (9-b)
  
print(f(N, K))

Submission status: Accepted

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


dp_small = [ [0]*5 for _ in range(keta+1)]
dp_same = [ [0]*5 for _ in range(keta+1)]

dp_small[0][0] = 0
dp_same[0][0] = 1

for i in range(keta):
    num = int(n[i])
    for j in range(4):
        dp_small[i+1][j+1] += dp_small[i][j] * 9
        dp_small[i+1][j] += dp_small[i][j]
        if num != 0:
            dp_small[i+1][j+1] += dp_same[i][j]*(num-1)
            dp_small[i+1][j] += dp_same[i][j]

        if num == 0:
            dp_same[i+1][j] += dp_same[i][j]
        else:
            dp_same[i+1][j+1] += dp_same[i][j]

print(dp_same[-1][k]+dp_small[-1][k])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

import functools

@functools.lru_cache(None)
def rec(i, k, is_same):
    if k == 0:
        return 1
    if i == 0:
        if k >= 2:
            return 0
        if is_same == 1:
            return int(S[len(S) - i - 1])
        else:
            return 9

    res = 0
    a = int(S[len(S) - i - 1])
    if is_same == 1:
        for x in range(a + 1):
            if x == a and x == 0:
                res += rec(i - 1, k, 1)
            elif x == 0:
                res += rec(i - 1, k, 0)
            elif x == a:
                res += rec(i - 1, k - 1, 1)
            else:
                res += rec(i - 1, k - 1, 0)
    else:
        for x in range(10):
            if x == 0:
                res += rec(i - 1, k, 0)
            else:
                res += rec(i - 1, k - 1, 0)
    return res

n = len(S)
res = rec(n - 1, K, 1)
print(res)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

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

def rec(i, k, is_same):
    if dp[i][k][is_same] != 0:
        return dp[i][k][is_same]
    if k == 0:
        return 1
    if i == 0:
        if k >= 2:
            return 0
        if is_same == 1:
            dp[i][k][is_same] = int(S[len(S) - i - 1])
        else:
            dp[i][k][is_same] = 9
        return dp[i][k][is_same]

    res = 0
    a = int(S[len(S) - i - 1])
    if is_same == 1:
        for x in range(a + 1):
            if x == a and x == 0:
                res += rec(i - 1, k, 1)
            elif x == 0:
                res += rec(i - 1, k, 0)
            elif x == a:
                res += rec(i - 1, k - 1, 1)
            else:
                res += rec(i - 1, k - 1, 0)
    else:
        for x in range(10):
            if x == 0:
                res += rec(i - 1, k, 0)
            else:
                res += rec(i - 1, k - 1, 0)

    dp[i][k][is_same] = res
    return res

n = len(S)
res = rec(n - 1, K, 1)
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def solve():
    S = Scanner.string()
    N = len(S)
    K = Scanner.int()
    dp = [[[0 for _ in range(2)] for _ in range(K + 1)] for _ 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):
                    ni, nj, nk = i + 1, j, 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[N][K][0] + dp[N][K][1])


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=list(input())
K=int(input())
N=list(map(int,N))
#print(N)
dp=[[[0 for _ in range(4)] for _ in range(len(N))] for _ in range(2)]
for i in range(len(N)):
    num=N[i]
    mayover=0
    if i==0:
        id=0
        for j in range(10):
            if j==num:
                id=1
            elif j>num:
                break
            if j==0:
                dp[id][i][0]=dp[id][i][0]+1
            else:
                dp[id][i][1] = dp[id][i][1] + 1
    else:
        for j in range(2):
            for l in range(4):
                if j==0:
                    dp[j][i][l] = dp[j][i][l] + dp[j][i - 1][l]
                    if l != 0:
                        dp[j][i][l] = dp[j][i][l] + 9*dp[j][i - 1][l - 1]
                else:
                    if num==0:
                        for l in range(4):
                            dp[j][i][l] = dp[j][i - 1][l]
                    else:
                        dp[0][i][l] = dp[0][i][l] + dp[j][i - 1][l]
                        if l != 0:
                            dp[0][i][l] = dp[0][i][l] + (num - 1) * dp[j][i - 1][l - 1]
                            dp[1][i][l] = dp[1][i][l] + dp[j][i - 1][l - 1]
    #print(dp[0][i],dp[1][i])
    #input()
print(dp[0][len(N)-1][K]+dp[1][len(N)-1][K])

Submission status: Accepted

Solution code:
N=list(input())
K=int(input())
N=list(map(int,N))
#print(N)
dp=[[[0 for _ in range(4)] for _ in range(len(N))] for _ in range(2)]
for i in range(len(N)):
    num=N[i]
    mayover=0
    if i==0:
        for j in range(10):
            if j<num:
                if j==0:
                    dp[0][i][0]=dp[0][i][0]+1
                else:
                    dp[0][i][1] = dp[0][i][1] + 1
            elif j==num:
                if j==0:
                    dp[1][i][0] = dp[1][i][0] + 1
                else:
                    dp[1][i][1] = dp[1][i][1] + 1
    else:

        for j in range(2):
            if j==0:
                for l in range(4):
                    dp[j][i][l] = dp[j][i][l] + dp[j][i - 1][l]
                    if l != 0:
                        dp[j][i][l] = dp[j][i][l] + 9*dp[j][i - 1][l - 1]
            else:
                if num==0:
                    for l in range(4):
                        dp[j][i][l]=dp[j][i-1][l]
                else:
                    for l in range(4):
                        dp[0][i][l]=dp[0][i][l]+dp[j][i-1][l]
                        if l!=0:
                            dp[0][i][l]=dp[0][i][l]+(num-1)*dp[j][i-1][l-1]
                            dp[1][i][l]=dp[1][i][l]+dp[j][i-1][l-1]

    #print(dp[0][i],dp[1][i])
    #input()
print(dp[0][len(N)-1][K]+dp[1][len(N)-1][K])

Submission status: Accepted

Solution code:
import sys
 
read = sys.stdin.read
 
 
def main():
    N, K = map(int, read().split())
 
    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]
            else:
                dp1[j] = 0
                dp2[j] = 1
 
    print(dp1[K] + dp2[K])
    return
 
 
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]

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

Submission status: Accepted

Solution code:
import math
n = int(input())
K = int(input())

def calk1(n):
    if n == 0: return 0
    m = int(math.log10(n))
    num = m * 9
    num += n//(10**m)
    return num

def calk2(n):
    m = int(math.log10(n))
    num = m * (m - 1) // 2 * 9**2
    num += (n//(10**m)-1) * m * 9
    num += calk1(n - (n//(10**m)*10**m))
    return num

def calk3(n):
    m = int(math.log10(n))
    num = m * (m - 1) * (m - 2) // 6 * 9**3
    num += (n//(10**m)-1) * (m * (m - 1) // 2 * 9**2)
    num += calk2(n - (n//(10**m)*10**m))
    return num
if n < 10 ** (K - 1): print(0)
else:
    if K == 1: print(calk1(n))
    elif K == 2: print(calk2(n))
    else: print(calk3(n))

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=input()
k=int(input())
if k==1:
    a=int(n[0])
    l=len(n)
    ans=9*(l-1)+a
elif k==2:
    a=int(n[0])
    A=len(n)
    for i in range(1,A):
        if n[i]!="0":
            b=int(n[i])
            B=A-i
            break
    else:
        B=1
        b=0
    ans=9*(a-1)*(A-1)+(B-1)*9+b
    for i in range(2,A):
        ans+=81*(i-1)
else:
    a=int(n[0])
    A=len(n)
    for i in range(1,A):
        if n[i]!="0":
            b=int(n[i])
            B=A-i
            for j in range(i+1,A):
                if n[j]!="0":
                    c=int(n[j])
                    C=A-j
                    break
            else:
                c=0
                C=1
            break
    else:
        c=b=0
        C=B=1
    ans=(a-1)*81*(A-1)*(A-2)//2+81*(B-1)*(B-2)//2+(b-1)*9*(B-1)+9*(C-1)+c
    for i in range(3,A):
        ans+=729*(i-1)*(i-2)//2
print(ans)

Submission status: Accepted

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


def run():
    dp = [[[0] * 4 for _ in range(2)] for _ in range(len(sN) + 1)]
    dp[0][0][0] = 1

    for i in range(len(sN)):
        for j in range(2):
            # j=0 : 現在の桁まで数字が同じ
            # j=1 : すでに小さい数値とわかっている

            # limには次の桁の数字の最大値を代入する
            lim = 9 if j == 1 else (ord(sN[i]) - ord('0'))
            for k in range(lim + 1):
                for l in range(4):
                    nl = l + int(k > 0)
                    if nl >= 4: continue
                    dp[i + 1][k < lim or j == 1][nl] += dp[i][j][l]

        # print(dp)

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


if __name__ == '__main__':
    run()

Submission status: Accepted

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


dp[0][0][1] = 1
for i in range(1, len_n+1):
    d = int(n[i-1])
    for j in range(K+1):
        dp[i][j][0] += dp[i-1][j][0]
        dp[i][j+1][0] += dp[i-1][j][0]*9
        if 0 < d:
            dp[i][j+1][0] += dp[i-1][j][1]*(d-1)
            dp[i][j][0] += dp[i-1][j][1]
            dp[i][j+1][1] += dp[i-1][j][1]
        else:
            dp[i][j][1] += dp[i-1][j][1]

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

Submission status: Accepted

Solution code:

def resolve():
    # 十進数表記で1~9までの数字がK個入るN桁の数字の数を答える問題
    S = input()
    K = int(input())
    n = len(S)

    # dp[i][k][smaller]:
    # i:桁数
    # K:0以外の数字を使った回数
    # smaller:iまでの桁で値以上になっていないかのフラグ

    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)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

dp[0][0][0] = 1
dp[0][1][0] = 0
dp[0][2][0] = 0
dp[0][3][0] = 0
dp[0][0][1] = 0
dp[0][1][1] = 0
dp[0][2][1] = 0
dp[0][3][1] = 0

for i in range(1, keta+1):
    n = int(str(N)[i-1])
    if n == 0:
        # 桁，0でない数字の数，未満フラグ
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][1][0] = dp[i-1][1][0]
        dp[i][2][0] = dp[i-1][2][0]
        dp[i][3][0] = dp[i-1][3][0]
        
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][1][1] = dp[i-1][1][1] + dp[i-1][0][1]*9
        dp[i][2][1] = dp[i-1][2][1] + dp[i-1][1][1]*9
        dp[i][3][1] = dp[i-1][3][1] + dp[i-1][2][1]*9
    elif n != 0:
        dp[i][0][0] = 0
        dp[i][1][0] = dp[i-1][0][0]
        dp[i][2][0] = dp[i-1][1][0]
        dp[i][3][0] = dp[i-1][2][0]
        
        dp[i][0][1] = dp[i-1][0][0] + dp[i-1][0][1]
        dp[i][1][1] = (dp[i-1][1][0]+dp[i-1][1][1]) \
                     + dp[i-1][0][0]*(n-1) + dp[i-1][0][1]*9
        dp[i][2][1] = (dp[i-1][2][0]+dp[i-1][2][1]) \
                     + dp[i-1][1][0]*(n-1) + dp[i-1][1][1]*9
        dp[i][3][1] = (dp[i-1][3][0]+dp[i-1][3][1]) \
                     + dp[i-1][2][0]*(n-1) + dp[i-1][2][1]*9
print(sum(dp[keta][K]))

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

read = sys.stdin.read


def com(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(n - r + 1, n + 1):
        numer = numer * i
    for i in range(1, r + 1):
        denom = denom * i
    return numer // denom


def main():
    N, K = map(int, read().split())

    S = str(N)
    L = len(S)

    @lru_cache(maxsize=None)
    def rec(i, k, smaller):
        if i == L:
            if k == 0:
                return 1
            else:
                return 0
        if k == 0:
            return 1
        if smaller:
            return com(L - i, k) * pow(9, k)
        if S[i] == '0':
            return rec(i + 1, k, False)

        ans = 0
        ans += rec(i + 1, k, True)
        ans += rec(i + 1, k - 1, True) * (int(S[i]) - 1)
        ans += rec(i + 1, k - 1, False)
        return ans

    ans = rec(0, K, False)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def com(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(n - r + 1, n + 1):
        numer = numer * i
    for i in range(1, r + 1):
        denom = denom * i
    return numer // denom


def main():
    N, K = map(int, read().split())

    S = str(N)
    L = len(S)

    @lru_cache(maxsize=None)
    def rec(i, k, smaller):
        if i == L:
            if k == 0:
                return 1
            else:
                return 0
        if k == 0:
            return 1
        if smaller:
            return com(L - i, k) * pow(9, k)
        if S[i] == '0':
            return rec(i + 1, k, False)

        ans = 0
        ans += rec(i + 1, k, True)
        ans += rec(i + 1, k - 1, True) * (int(S[i]) - 1)
        ans += rec(i + 1, k - 1, False)
        return ans

    ans = rec(0, K, False)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

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

    @lru_cache(None)
    def F(n, k):

        if n < 10:
            if 1 < k:
                return 0
            elif k == 1:
                return n
            elif k == 0:
                return 1

        m, r = divmod(n, 10)
        ret = 0
        # rに応じて場合分け
        if k >= 1:
            ret += F(m, k-1)*r  # r<=k
            ret += F(m-1, k-1)*(9-r)  # r>k
        ret += F(m, k)*1  # r==0
        return ret
    print(F(n, k))


resolve()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read


def main():
    N, K = map(int, read().split())

    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]
            else:
                dp1[j] = 0
                dp2[j] = 1

    print(dp1[K] + dp2[K])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read


def main():
    N, K = map(int, read().split())

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

    for x in map(int, str(N)):
        dp1, dp1_prev = [0] * (K + 1), dp1
        dp2, dp2_prev = [0] * (K + 1), dp2
        for j in range(K, -1, -1):
            if j > 0:
                dp2[j] = dp2_prev[j - 1] * 9
                if x != 0:
                    dp2[j] += dp1_prev[j - 1] * (x - 1)
            dp2[j] += dp2_prev[j]
            if x != 0:
                dp2[j] += dp1_prev[j]
                
            if x != 0:
                if j > 0:
                    dp1[j] = dp1_prev[j - 1]
            else:
                dp1[j] = dp1_prev[j]

    print(dp1[K] + dp2[K])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K = map(int, read().split())

    X = list(map(int, str(N)))
    L = len(X)

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

    for i, x in enumerate(X):
        for j in range(K + 1):
            if x != 0:
                if j > 0:
                    dp1[i + 1][j] = dp1[i][j - 1]
            else:
                dp1[i + 1][j] = dp1[i][j]
            if j > 0:
                dp2[i + 1][j] = dp2[i][j - 1] * 9
                if x != 0:
                    dp2[i + 1][j] += dp1[i][j - 1] * (x - 1)
            dp2[i + 1][j] += dp2[i][j]
            if x != 0:
                dp2[i + 1][j] += dp1[i][j]

    print(dp1[L][K] + dp2[L][K])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = input()
    L = len(N)
    K = int(input())
    dp = [[0 for _ in range(L + 1)] for _ in range(K + 1)]
    dpp = [[0 for _ in range(L + 1)] for _ in range(K + 1)]
    dpp[0][0] = 1
    for i in range(1, L + 1):
        n = int(N[i - 1])
        for k in range(K + 1):
            # from dpp
            kk = k + (1 if n > 0 else 0)
            if kk <= K:
                dpp[kk][i] = dpp[k][i - 1]
            if n > 0:
                dp[k][i] += dpp[k][i - 1]
                if k + 1 <= K:
                    dp[k + 1][i] += (n - 1) * dpp[k][i - 1]
            # from dp
            dp[k][i] += dp[k][i - 1]
            if k + 1 <= K:
                dp[k + 1][i] += 9 * dp[k][i - 1]
    print(dp[K][L] + dpp[K][L])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

# dp[is未満][K][桁]
dp = [[[0] * len(N) for _ in range(K+1)] for _ in range(2)]
dp[0][0][0] = 0
dp[1][0][0] = 1
dp[0][1][0] = 1
dp[1][1][0] = max(0,int(N[0])-1)

man_k = 1
for i in range(1, len(N)):
    n = N[i]
    is_nonzero = 1 if n != '0' else 0
    man_k += is_nonzero
    if man_k <= K:
        dp[0][man_k][i] = dp[0][man_k-is_nonzero][i-1]

    dp[1][0][i] = dp[1][0][i-1]
    for k in range(1,K+1):
        dp[1][k][i] = dp[1][k][i-1] + dp[1][k-1][i-1] * 9 # n==0のパターンとn!=0のパターン
        if n != "0":
            dp[1][k][i] += dp[0][k-1][i-1] * (int(n)-1) + dp[0][k][i-1] 

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
MAXN = 100

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

dl = [[None] * (MAXN + 1) for _ in range(MAXN + 1)]
de = [[None] * (MAXN + 1) for _ in range(MAXN + 1)]


def n_num_e(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        if i == 0:
            return 1
        else:
            return 0
    elif de[d][i] is not None:
        return de[d][i]
    else:
        if int(n[d - 1]) == 0:
            result = n_num_e(d - 1, i)
        else:
            result = n_num_e(d - 1, i - 1)
        de[d][i] = result
        return result


def n_num_l(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        return 0
    elif dl[d][i] is not None:
        return dl[d][i]
    else:
        if int(n[d - 1]) == 0:
            ne = 0
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl
        else:
            ne = (int(n[d - 1]) - 1) * n_num_e(d - 1, i - 1) + n_num_e(d - 1, i)
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl

        dl[d][i] = result
        return result


answer = n_num_e(len(n), k) + n_num_l(len(n), k)
print(answer)

Submission status: Accepted

Solution code:
n = input()
k = int(input())
l = len(n)
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):
    for j in range(2):
        for o in range(k + 1):
            for m in range(10):
                if not j and m > int(n[i]):
                    continue
                f = j or m < int(n[i])
                o2 = o + (m != 0)
                if o2 > k:
                    continue
                dp[i + 1][f][o2] += dp[i][j][o]
print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7   
N = readline().decode().rstrip()
K = int(readline())
L = len(N)
# 桁DP
dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(L+1)]
dp[0][0][0] = 1
for i in range(L):
    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]
print(dp[L][K][0]+dp[L][K][1])

Submission status: Accepted

Solution code:
N=int(input())
K=int(input())
#for i in range(100):
 # for j in range(100):
  #  for k in range(100):
   #   if(i!=j and i!=k and j!=k):
    #    if(i*(10**))
ans=0
if(K==3):
  for a in range(1,10):
    for b in range(1,10):
      for c in range(1,10):
        ap=0
        bp=0
        cp=0
        while(a*(10**ap)<=N):#aについてみる
          ap+=1
        ap-=1
        while(a*(10**ap)+b*(10**bp)<=N and bp<ap):#bについてみる
          bp+=1
        bp-=1
        while(a*(10**ap)+b*(10**bp)+c*(10**cp)<=N and cp<bp):#cについてみる
          cp+=1
        cp-=1
        ans+=1+cp+(bp*(bp-1))//2+(ap*(ap-1)*(ap-2))//6
  print(ans)
elif(K==2):
  ans=0
  for i in range(100):
    for j in range(100):
      if(i>j):
        for a in range(1,10):
          for b in range(1,10):
            if(a*(10**i)+b*(10**j)<=N):
              ans+=1
  print(ans)
else:
  ans=0
  for i in range(100):
    for a in range(1,10):
      if(a*(10**i)<=N):
        ans+=1
  print(ans)

Submission status: Accepted

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

len_n=len(n)
dp0=[[0]*(k+1) for _ in range(len_n+1)]
dp1=[[0]*(k+1) for _ in range(len_n+1)]
dp0[0][0]=1
# dp0: N以下であることが未確定
# dp1: N以下であることが確定
for i, n_i in enumerate(n):
    for k_i in range(k+1):
        if n_i=='0':
            dp0[i+1][k_i]+=dp0[i][k_i]
            dp1[i+1][k_i]+=dp1[i][k_i]
            if k_i<k:
                dp1[i+1][k_i+1]+=9*dp1[i][k_i]
        else:
            if k_i<k:
                dp0[i+1][k_i+1]+=dp0[i][k_i]
                dp1[i+1][k_i+1]+=(int(n_i)-1)*dp0[i][k_i]
                dp1[i+1][k_i+1]+=9*dp1[i][k_i]
            dp1[i+1][k_i]+=dp0[i][k_i]
            dp1[i+1][k_i]+=dp1[i][k_i]

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

Submission status: Accepted

Solution code:
import sys 
from functools import lru_cache
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
N = int(readline())
K = int(readline())
@lru_cache(None)
def f(N,K):
    if K == -1:
        return 0
    if N < 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0
    ans = 0
    q, mod = divmod(N, 10)
    ans += f(q,K) + mod * f(q,K-1) + (9-mod) * f(q-1,K-1) 
    return ans
print(f(N,K))

Submission status: Accepted

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

dp=[[[0 for _ in range(2)] for _ in range(5)] for _ in range(l+1)]

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

for i in range(1,l):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=9*dp[b][j][1]
print(dp[l-1][k][0]+dp[l-1][k][1])

Submission status: Accepted

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

dp =[[[ 0 for _ in range(2)] for _ in range(5)] for _ in range(len(N)+1)]
# dp[i][j][flg] i+1桁目までで0以外の個数がj個
# flg = 1 -> N 以下が確定している

dp[0][1][1] = int(N[0])-1
dp[0][1][0] = 1
dp[0][0][1]=1
for i in range(1,L):
  for j in range(4):
    b = i-1 # hitotumae
    now = int(N[i])
    ## N上限に張り付いてる方
    if now == 0:
      dp[i][j][0] += dp[b][j][0]
    else:
      dp[i][j][1] += dp[b][j][0]
      dp[i][j+1][1] += dp[b][j][0] * (now-1)
      dp[i][j+1][0] += dp[b][j][0]
    ## 張り付いてない方
    dp[i][j][1] += dp[b][j][1]
    dp[i][j+1][1] += dp[b][j][1] * 9
  

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

Submission status: Accepted

Solution code:
n=input()
k=int(input())
l=len(n)
dp=[[[0 for _ in range(2)] for _ in range(5)] for _ in range(l+1)]
dp[0][1][1]=int(n[0])-1
dp[0][1][0]=1
for i in range(1,l):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=dp[b][j][1]*9
  dp[i][1][1]+=9
print(dp[l-1][k][0]+dp[l-1][k][1])