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
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7

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

    # has less number before
    dp0 = [[0]*5 for _ in range(lenN+1)]
    # not had yet
    dp1 = [[0]*5 for _ in range(lenN+1)]
    dp1[0][0] = 1

    for i in range(lenN):
        k = int(N[i])
        for zero in range(4):
            dp0[i+1][zero] += dp0[i][zero]
            dp0[i+1][zero+1] += dp0[i][zero] * 9
            if k != 0:
                dp0[i+1][zero] += dp1[i][zero]
                dp0[i+1][zero+1] += dp1[i][zero] * (k-1)
                dp1[i+1][zero+1] += dp1[i][zero]
            else:
                dp1[i+1][zero] += dp1[i][zero]


    ans = dp0[lenN][K] + dp1[lenN][K]
    print(ans)



if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

for i in range(1,L+1):
    a = int(N[i-1])
    for k in range(K+1):
        dp[i][0][k] += dp[i-1][0][k] if a==0 else dp[i-1][0][k-1]
        dp[i][1][k] += dp[i-1][1][k-1]*9 + dp[i-1][1][k]
        if a>0:
            dp[i][1][k] += dp[i-1][0][k-1]*(a-1) + dp[i-1][0][k]

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

Submission status: Accepted

Solution code:
s = input()
k = int(input())
l = len(s)
dp = [[[0 for i in range(k+1)] for j in range(2)] for m in range(l+1)]
dp[0][0][0] = 1
for i in range(l):
    for x in range(k+1):
        if s[i] == "0":
            dp[i+1][0][x] += dp[i][0][x]
        else:
            if x < k:
                dp[i+1][0][x+1] += dp[i][0][x]
            dp[i+1][1][x] += dp[i][0][x]
        for j in range(1, int(s[i])):
            if x < k:
                dp[i+1][1][x+1] += dp[i][0][x]
        dp[i+1][1][x] += dp[i][1][x]
        for j in range(1, 10):
            if x < k:
                dp[i+1][1][x+1] += dp[i][1][x]
print(dp[-1][0][-1] + dp[-1][1][-1])

Submission status: Accepted

Solution code:
N = str(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)):
  n = int(N[i])
  for j in range(K+1):
    for k in range(2): # smaller(未満なら1)
      for l in range(10): 
        nj, nk = j, 0
        if k == 0 and l == n:
          nk = 0
        elif k == 0 and l < n:
          nk = 1
        elif k == 0 and l > n:
          continue
        
        if k == 1:
          nk = 1
        
        if l != 0:
          if j < K:
            nj += 1
          else:
            continue
        
        dp[i+1][nj][nk] += dp[i][j][k]

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

Submission status: Accepted

Solution code:
N = input()
K = int(input())
dp = [[[0 for k in range(K+2)] for j in range(2)] for i in range(len(N)+1)]
dp[0][0][0] = 1
for i in range(len(N)):
    Ni = int(N[i])
    for j in range(2):
        for k in range(K+1):
            for d in range(10 if j else int(Ni)+1):
                dp[i+1][j or (d < Ni)][k + (d != 0)] += dp[i][j][k]
                # print(i, j, k, d)

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

Submission status: Accepted

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

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

for i in range(len(n)):
    for j in range(k + 1):
        dp0[i + 1][j] += dp0[i][j]
        dp0[i + 1][j + 1] += dp0[i][j] * 9
        if n[i] != '0':
            dp0[i + 1][j] += dp1[i][j]
            dp0[i + 1][j + 1] += dp1[i][j] * (int(n[i]) - 1)
            dp1[i + 1][j + 1] += dp1[i][j]
        elif n[i] == '0':
            dp1[i + 1][j] += dp1[i][j]

print(dp0[len(n)][k] + dp1[len(n)][k])

Submission status: Accepted

Solution code:
strN = input().rstrip()
K = int(input())

maxD = len(strN)

dp = [[[0]*(K+1) for j in range(2)] for i in range(maxD+1)]
dp[0][0][0] = 1
for d, Nd in enumerate(strN):
    Nd = int(Nd)
    for isLtN in range(2):
        for numNot0 in range(K+1):
            for x in range(10):
                if not isLtN and x > Nd: continue
                isLtN2 = isLtN or x < Nd
                numNot02 = numNot0 + (x != 0)
                if numNot02 > K: continue
                dp[d+1][isLtN2][numNot02] += dp[d][isLtN][numNot0]

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ins()
K = ini()


def solve():
    M = len(N)
    dp_eq = [[0 for _ in range(K + 1)] for _ in range(M)]
    dp_less = [[0 for _ in range(K + 1)] for _ in range(M)]

    dp_eq[0][K - 1] = 1
    dp_less[0][K] = 1
    dp_less[0][K - 1] = ord(N[0]) - ord("0") - 1
    for i in range(1, M):
        is_zero = N[i] == "0"
        for k in range(K + 1):
            if is_zero:
                dp_eq[i][k] = dp_eq[i - 1][k]
            elif k < K:
                dp_eq[i][k] = dp_eq[i - 1][k + 1]

            dp_less[i][k] = dp_less[i - 1][k]
            if k < K:
                dp_less[i][k] += dp_less[i - 1][k + 1] * 9
            if not is_zero:
                dp_less[i][k] += dp_eq[i - 1][k]
                if k < K:
                    dp_less[i][k] += dp_eq[i - 1][k + 1] * (ord(N[i]) - ord("0") - 1)
    return dp_eq[M - 1][0] + dp_less[M - 1][0]


print(solve())

Submission status: Accepted

Solution code:
n = list(input())
k = int(input())
t = len(n)
ketaDP = [[[0 for i in range(2)] for j in range(k+1)] for u in range(t)]
#ketaDP = [上から何桁目][0以外が何回出てる][nより小さいの確定？]
ketaDP[0][0][0] = 1
ketaDP[0][1][0] = int(n[0])-1
ketaDP[0][1][1] = 1
for i in range(1,t):
    now = int(n[i])
    for j in range(k+1):
        ketaDP[i][j][0] += ketaDP[i-1][j][0]
    for j in range(k):
        ketaDP[i][j+1][0] += ketaDP[i-1][j][0] * 9
    if now == 0:
        for j in range(k+1):
            ketaDP[i][j][1] += ketaDP[i-1][j][1]
    elif now != 0:
        for j in range(k+1):
            ketaDP[i][j][0] += ketaDP[i-1][j][1]
        for j in range(k):
            ketaDP[i][j+1][1] += ketaDP[i-1][j][1]
            ketaDP[i][j+1][0] += ketaDP[i-1][j][1]*(now-1)
print(sum(ketaDP[t-1][k]))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = input()
k = int(input())
l = len(n)
dp1 = [[0]*(k+1) for _ in range(l+1)]
dp0 = [[0]*(k+1) for _ in range(l+1)]
dp1[0][0] = 1
dp0[0][0] = 0
for i in range(1, l+1):
    for j in range(0, k+1):
        if n[i-1]=="0":
            dp1[i][j] = dp1[i-1][j]
        else:
            if j>=1:
                dp1[i][j] = dp1[i-1][j-1]
            dp0[i][j] += dp1[i-1][j]
        if int(n[i-1])>=2 and j>=1:
            dp0[i][j] += dp1[i-1][j-1] * (int(n[i-1])-1)
        if j>=1:
            dp0[i][j] += dp0[i-1][j-1]*9
        dp0[i][j] += dp0[i-1][j]
print(dp0[l][k]+dp1[l][k])

Submission status: Accepted

Solution code:
N = list(map(int, list(input())))
L = len(N)
K = int(input())
 
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):
    ni = N[i]
    if ni == 0:
        for j in range(K):
            dp[i+1][1][j+1] += dp[i][1][j] * 9
        for j in range(K+1):
            dp[i+1][0][j] += dp[i][0][j]
    else:
        for j in range(K+1):
            dp[i+1][1][j] += dp[i][0][j]
        for j in range(K):
            dp[i+1][1][j+1] += (dp[i][0][j] * (ni-1) + dp[i][1][j] * 9)
            dp[i+1][0][j+1] += dp[i][0][j]
 
    for j in range(K+1):
        dp[i+1][1][j] += dp[i][1][j]
 
print(dp[L][0][K]+dp[L][1][K])

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

# ABC154 E - Almost Everywhere Zero
"""
N = '9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999'
K = 3
L = len(N)
"""

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

def judge(a):
    return a != 0

# N以下の数字で条件を満たす桁がk個のもの
def digit_dp(n, k):
    l = len(n)

    dp = [[[0] * (k + 1) for _ in range(2)] for i in range(l + 1)]
    dp[0][0][0] = 1

    for i in range(l):
        d = int(n[i])

        for j in range(2):
            for d_j in range(10 if j else d + 1):
                for k_j in range(k + 1):
                    if judge(d_j):
                        if k_j + 1 <= k:
                            dp[i + 1][j | (d_j < d)][k_j + 1] += dp[i][j][k_j]
                    else:
                        dp[i + 1][j | (d_j < d)][k_j] += dp[i][j][k_j]

    return dp

dp = digit_dp(N, K)
print(dp[L][0][K] + dp[L][1][K])

# ABC029 D - 1
"""
N = '999999999'
L = len(N)

def judge_2(a):
    return a == 1

# N以下の数字の中で「1が書いてある桁がk個ある数字」がいくつあるか
# 上のものと関数の中身自体は変えていない
def digit_dp_2(n, k):
    l = len(n)

    dp = [[[0] * (k + 1) for _ in range(2)] for i in range(l + 1)]
    dp[0][0][0] = 1

    for i in range(l):
        d = int(n[i])

        for j in range(2):
            for d_j in range(10 if j else d + 1):
                for k_j in range(k + 1):
                    if judge_2(d_j):
                        if k_j + 1 <= k:
                            dp[i + 1][j | (d_j < d)][k_j + 1] += dp[i][j][k_j]
                    else:
                        dp[i + 1][j | (d_j < d)][k_j] += dp[i][j][k_j]

    return dp

dp = digit_dp_2(N, L)

ans = 0
for j in range(L + 1):
    # dp[l]について各j(1のカウント)の通りの数 * j
    ans += (dp[L][0][j] + dp[L][1][j]) * j
print(ans)
"""

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

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

def judge(a):
    return a == 0

# N以下の数字で条件を満たす桁がk個のもの
def digit_dp(n, k):
    l = len(n)

    dp = [[[0] * (k + 1) for _ in range(2)] for i in range(l + 1)]
    dp[0][0][0] = 1

    for i in range(l):
        d = int(n[i])

        for j in range(2):
            for d_j in range(10 if j else d + 1):
                for k_j in range(k + 1):
                    # 0じゃない数字が混じっていれば数字は進む
                    if not judge(d_j):
                        # 求めたい個数以下なら
                        if k_j + 1 <= k:
                            dp[i + 1][j | (d_j < d)][k_j + 1] += dp[i][j][k_j]
                    else:
                        dp[i + 1][j | (d_j < d)][k_j] += dp[i][j][k_j]

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

print(digit_dp(N, K))

Submission status: Accepted

Solution code:
# from collections import defaultdict
import math

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

N = int(input())
K = int(input())
keta = len(str(N))
dp = [[0]*(keta) for i in range(4)]
ans = 0

for k in range(1, 4):
    for i in range(1, keta):
        if i<k:
            continue
        else:
            dp[k][i] = comb(i-1, i-k)*(9**k)
#print(dp)
# dp[k][i]: i桁で、k個の0でない数            

ans += sum(dp[K]) # (N の桁)-1 までの累積和

count = 0

for j in range(keta):
    t = int(str(N)[j])
    

    if j==0:
        count+=1
        ans += sum(dp[K-count])*(t-1)
        if count == K: # K==1
            ans+=t
            break
        continue
        
    elif j==keta-1:
        if t!=0:
            count+=1
        if count==K:
            ans+=t
        break
        
        
    if t !=0:
        count+=1
        if count==K:
            ans+=sum(dp[K-count+1][:keta-j]) #0のとき
            ans+=t
            break
        
        ans += sum(dp[K-count][:keta-j])*(t-1)  #0より大きいとき
        ans += sum(dp[K-count+1][:keta-j])   #0のとき
        
   
        
print(ans)

Submission status: Accepted

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

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):
    ni = N[i]
    if ni == 0:
        for j in range(K):
            dp[i+1][1][j+1] += dp[i][1][j] * 9
        for j in range(K+1):
            dp[i+1][0][j] += dp[i][0][j]
    else:
        for j in range(K+1):
            dp[i+1][1][j] += dp[i][0][j]
        for j in range(K):
            dp[i+1][1][j+1] += (dp[i][0][j] * (ni-1) + dp[i][1][j] * 9)
            dp[i+1][0][j+1] += dp[i][0][j]

    for j in range(K+1):
        dp[i+1][1][j] += dp[i][1][j]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://atcoder.jp/contests/tdpc/tasks/tdpc_number
    # https://atcoder.jp/contests/tdpc/submissions/14489469
    n = input()
    d=int(input())
    # dp[ i ][ smaller ][ d ] := i 桁目までで 0 以外の数の使用数dである数の個数


    dp = [[[0] * (d+2) for _ in range(2)] for _ in range(len(n) + 1)]
    dp[0][0][0] = 1
    
    MOD = 10**9 + 7
    for i in range(len(n)):
        c = ord(n[i]) - ord('0')
        for j in range(d+1):
            # small->small
            dp[i+1][1][j+1]+=dp[i][1][j]*9
            dp[i+1][1][j]+=dp[i][1][j]

            # else->small
            if c>0: # i桁めが0以外
                dp[i + 1][1][j+1]+=dp[i][0][j]*(c-1) #i+1桁目が0以外
                dp[i + 1][1][j]+=dp[i][0][j]#0
            

            # else->else
            if c>0:
                dp[i + 1][0][j+1]+=dp[i][0][j]
            else:
                dp[i+1][0][j]+=dp[i][0][j]
                dp[i + 1][0]
    
    print(dp[len(n)][1][d] + dp[len(n)][0][d])
    
    
    
resolve()

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

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
  dp[i][1][1] += 9 # i桁目から始まった物（それより上がZEROのもの。）

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

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    n = input()
    k = ni()

    l = len(n)

    dp_true = [[0 for _ in range(k + 2)] for i in range(l + 1)]
    dp_false = [[0 for i in range(k + 2)] for j in range(l + 1)]
    dp_false[0][0] = 1

    for i in range(l):
        num = int(n[i])

        for j in range(k + 1):
            dp_true[i + 1][j] += dp_true[i][j]
            dp_true[i + 1][j + 1] += dp_true[i][j] * 9

            if num > 0:
                dp_true[i + 1][j + 1] += dp_false[i][j] * (num - 1)
                dp_true[i + 1][j] += dp_false[i][j]

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

    print(dp_true[l][k] + dp_false[l][k])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x

#ABC145-E
def kdp(s,K):#s(str)以下の非負整数で条件をK桁満たすものの個数
    #K: 条件を満たすべき桁数 O(桁数*条件を満たすべき桁数*10)
    
    #mod = 1000000007
    keta=len(s)
    dp=[[[0,0] for _ in range(K+1)] for _ in range(keta+1)]
    #dp[i][j][k]前からi桁目まで決め、j個の条件を満たす桁を含み、k=1:i文字目まで一致 k=0:対象の数以下

    dp[0][0][0]=1
    for i in range(0,keta):
        ni=i+1
        nd=int(s[i])
        for j in range(0,K+1):
            for k in range(0,2):  
                for d in range(10): 
                    nj=j
                    nk=k
                    if d!=0:#この辺に条件
                        nj+=1
                    if nj>K:continue
                    if k==0:
                        if d>nd:
                            break
                        elif d<nd:
                            nk=1
                    dp[ni][nj][nk]+=dp[i][j][k]

    ans=dp[keta][K][1]+dp[keta][K][0]
    #与えられた数未満で条件を満たすもの+与えられた数が条件を満たす場合1
    print(ans)

if __name__ == "__main__":
    s = input()
    K= int(input())#条件を満たすべき桁数
    kdp(s,K)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    s = input()
    K= int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    keta=len(s)
    dp=[[[0,0] for _ in range(K+1)] for _ in range(keta+1)]
    #dp[i][j][k]前からi桁目まで決め、j個の条件を満たす桁を含み、k=1:i文字目まで一致 k=0:対象の数以下

    dp[0][0][0]=1
    for i in range(0,keta):
        ni=i+1
        nd=int(s[i])
        for j in range(0,K+1):
            for k in range(0,2):  
                for d in range(10): 
                    nj=j
                    nk=k
                    if d!=0:nj+=1
                    if nj>K:continue
                    if k==0:
                        if d>nd:break
                        elif d<nd:nk=1
                    dp[ni][nj][nk]+=dp[i][j][k]
    if K<=keta:
        ans=dp[keta][K][1]+dp[keta][K][0]
    else:
        ans=0
        #与えられた数未満で条件を満たすもの+与えられた数が条件を満たす場合1
    print(ans)
    #print(dp)


    
    

        
    



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    s = input()
    K= int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    keta=len(s)
    dp=[[[0,0] for _ in range(keta+1)] for _ in range(keta+1)]
    #dp[i][j][k]前からi桁目まで決め、j個の条件を満たす桁を含み、k=1:i文字目まで一致 k=0:対象の数以下

    dp[0][0][0]=1
    for i in range(0,keta):
        ni=i+1
        nd=int(s[i])
        for j in range(0,keta):
            for k in range(0,2):  
                for d in range(10): 
                    nj=j
                    nk=k
                    if d!=0:nj+=1
                    if k==0:
                        if d>nd:break
                        elif d<nd:nk=1
                    dp[ni][nj][nk]+=dp[i][j][k]
    if K<=keta:
        ans=dp[keta][K][1]+dp[keta][K][0]
    else:
        ans=0
        #与えられた数未満で条件を満たすもの+与えられた数が条件を満たす場合1
    print(ans)
    #print(dp)


    
    

        
    



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = input()
    K= int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    keta=100+1
    dp=[[0]*(keta+1) for _ in range(keta+1)]
    dp[0][0]=1

    for i in range(1,keta+1):
        for j in range(0,i+1):
            dp[i][j]+=dp[i-1][j]+dp[i-1][j-1]*9
    l=len(N)
    cur0=0
    tot=0
    for i,si in enumerate(N):
        n=int(si)
        if n!=0:
            tot+=(n-1)*dp[l-1-i][K-i-1+cur0]+dp[l-1-i][K-i+cur0]
        else:
            cur0+=1
    ic=0
    for s in N:
        if s!='0':ic+=1
    if ic==K:tot+=1
    print(tot)
    

        
    



if __name__ == "__main__":
    main()

Submission status: Accepted

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

def pow(a,n):
    ans = 1
    while n > 1:
        if bin(a&1)==bin(1):
            ans = ans*a
        a = a*a
        n = n>>1
    return ans

def com(N,k):
    if k<0 or k>N: return 0
    if k==1:return N
    elif k==2: return N*(N-1)//2
    else: return N*(N-1)*(N-2)//6

S = len(str(N))
N = str(N)
def helper(i,k,smaller):
    if i==S:
        if k==0: return 1
        else: return 0
    if k ==0: return 1
    if smaller: return com(S-i,k)*(9**k)
    else:
        if N[i]=='0': return helper(i+1,k,False)
        else:
            zero = helper(i+1,k,True)
            a = helper(i+1,k-1,True)*(int(N[i])-1)
            b = helper(i+1,k-1,False)
            return zero + a + b
print(helper(0,K,False))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N=input().strip("\n")
    K=int(input())
    # dp[i][j][k]=i桁目 j: nonzero数　k:N以下確定か
    dp=[[[0]*(2) for i in range(K+1)] for j in range(len(N))]
    dp[0][0][1]=1
    dp[0][1][1]=int(N[0])-1
    dp[0][1][0]=1
    for i in range(len(N)):
        dp[i][0][1]=1
    for i in range(1,len(N)):
        d=int(N[i])
        for j in range(1,K+1):
            if d!=0:
                dp[i][j][1]=dp[i-1][j-1][1]*9+dp[i-1][j-1][0]*(d-1)
                # nonzeroを使う場合i-1で既にN以下確定なら好き勝手できる*9
                
                dp[i][j][1]+=dp[i-1][j][1]+dp[i-1][j][0]
                # zeroを使う場合
                
                dp[i][j][0]=dp[i-1][j-1][0]
                # d未満とったら確定するため。
            else:
                dp[i][j][1]=dp[i-1][j-1][1]*9+dp[i-1][j][1]                
                dp[i][j][0]=dp[i-1][j][0]
    print(sum(dp[len(N)-1][K]))
    
        
    
if __name__=="__main__":
    main()