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
sys.setrecursionlimit(10000)

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


def doit(n, k):
    if len(n) == 0:
        return k == 0
    d = int(n[0])
    if (n, k) not in m:
        ret = 0
        for i in range(d + 1):
            if i == d:
                ret += doit(n[1:], k - 1 if i > 0 else k)
            else:
                ret += doit('9' * (len(n) - 1), k - 1 if i > 0 else k)
        m[(n, k)] = ret
    return m[(n, k)]


print(doit(n, k))

Submission status: Accepted

Solution code:
from itertools import combinations
N=input()
K=int(input())
L = len(N)
dp = [[[0]*(L+1) for _ in range(K+2)] for _ in range(2)]
#dp[smaller][j][i]:=上からiケタ目までを確定したときの場合の数
#smaller = 0: 一致
#j: 0意外の数

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

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

Submission status: Accepted

Solution code:
def nCk(n, k):
    if k > n or min(n, k) < 0:
        return 0
    res = 1
    for i in range(1, k + 1):
        res = res * (n - i + 1) // i
    return res

def solveSmaller():
    return 9 ** k * nCk(n - 1, k)

def solveDp():
    global k
    dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n)]  # i, used k, smaller
    dp[0][1][0] = 1
    dp[0][1][1] = int(s[0]) - 1
    cnt = 1
    for i in range(1, n):
        cnt += s[i] != '0'
        for k in range(1, k + 1):
            dp[i][k][0] = cnt == k
            dp[i][k][1] = dp[i - 1][k][1] + \
                          (dp[i - 1][k][0] if s[i] != '0' else 0) + \
                          dp[i - 1][k - 1][1] * 9 + \
                          dp[i - 1][k - 1][0] * max(0, int(s[i]) - 1)
    return dp[n - 1][k][0] + dp[n - 1][k][1]

s = input()
k = int(input())
n = len(s)
print(solveSmaller() + solveDp())

Submission status: Accepted

Solution code:
n = list(reversed(input()))
k = int(input())
dp1 = [1] + [0] * 3
dp2 = [1] + [0] * 3
for i in range(len(n)):
    newdp1 = [0] * 4
    newdp2 = [0] * 4
    for j in range(4):
        newdp2[j] += dp2[j]
        if j > 0:
            newdp2[j] += dp2[j - 1] * 9
        d = int(n[i])
        if d == 0:
            newdp1[j] += dp1[j]
        else:
            newdp1[j] += dp2[j]
        if j > 0:
            if d > 0:
                newdp1[j] += dp1[j - 1]
                newdp1[j] += dp2[j - 1] * (d - 1)
    dp1 = newdp1
    dp2 = newdp2
print(dp1[k])

Submission status: Accepted

Solution code:
str_n = input()
keta = len(str_n)
not_zero = int(input())

dp = [[[0]*(not_zero+2) for _ in range(2)] for _ in range(keta+1)]
first = int(str_n[0])
dp[1][1][0] = 1
for k in range(1,10):
    if first == k:
        dp[1][0][1] += 1
    elif first > k:
        dp[1][1][1] += 1

for i in range(1,keta):
    # smallerからsmallerへの遷移
    for j in range(not_zero+1):
        # i桁目をゼロにする
        dp[i+1][1][j] += dp[i][1][j]
        # i桁目でゼロ以外を使う
        dp[i+1][1][j+1] += (dp[i][1][j])*9

    nex = int(str_n[i])
    # sameからsmallerへの遷移
    if not nex == 0:
        for j in range(not_zero+1):
            # i桁目をぜろにする
            dp[i+1][1][j] += dp[i][0][j]
            # i桁目でゼロ以外
            dp[i+1][1][j+1] += (dp[i][0][j]) * (nex-1)
    
    # sameからsameへの遷移
    if nex == 0:
        for j in range(not_zero+1):
            dp[i+1][0][j] = dp[i][0][j]
    else:
        for j in range(not_zero):
            dp[i+1][0][j+1] = dp[i][0][j]

print(dp[keta][1][not_zero] + dp[keta][0][not_zero])

Submission status: Accepted

Solution code:
n=input()
ln=len(n)
nn=[-1,-1,-1]
nnn=[0,0,0]
j=0
for i in range(ln):
  if n[i]!="0":
    nn[j]=i
    nnn[j]=int(n[i])
    j+=1
    if j==3:
      break

s=[9*(ln-1),81*(ln-1)*(ln-2)//2,729*(ln-1)*(ln-2)*(ln-3)//6]
s[0]+=nnn[0]
s[1]+=(nnn[0]-1)*9*(ln-1)+(0 if nn[1]==-1 else nnn[1]+9*(ln-nn[1]-1))
s[2]+=(nnn[0]-1)*81*(ln-1)*(ln-2)//2
s[2]+=(0 if nn[1]==-1 else (nnn[1]-1)*9*(ln-nn[1]-1)+81*(ln-nn[1]-1)*(ln-nn[1]-2)//2)+(0 if nn[2]==-1 else nnn[2]+9*(ln-nn[2]-1))

k=int(input())
print(s[k-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc154/tasks/abc154_e
# 桁DPっぽいよなぁ => O

"""
memo
dp0[i][j]
  上からi桁目まで決めて，0でない桁がj個あり
  Nより小さいことが確定している (less)
dp1[i][j]
  上からi桁目まで決めて，0でない桁がj個あり
  Nより小さいことが確定していない (i桁目まで同じ)

通常の再帰
rec
"""

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


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

# i桁目まで
for i in range(N):
    dig = int(S[i])

    # 0でない桁の個数がj個
    for j in range(K + 1): 
        # 選ぶ数字がk=0..9
        for k in range(10):
            nj = j if k == 0 else j + 1
            if k < dig:
                dp1[i + 1][nj] += dp0[i][j] + dp1[i][j]
            elif k == dig:
                dp1[i + 1][nj] += dp1[i][j]
                dp0[i + 1][nj] += dp0[i][j]
            else:
                dp1[i + 1][nj] += dp1[i][j]

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc154/tasks/abc154_e
# 桁DPっぽいよなぁ => O

"""
memo
dp0[i][j]
  上からi桁目まで決めて，0でない桁がj個あり
  Nより小さいことが確定している (less)
dp1[i][j]
  上からi桁目まで決めて，0でない桁がj個あり
  Nより小さいことが確定していない (i桁目まで同じ)

通常の再帰
rec
"""

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

def com(N, R):
    if R < 0 or R > N:
        return 0
    if R == 1:
        return N
    elif R == 2:
        return N * (N - 1) // 2
    elif R == 3:
        return N * (N - 1) * (N - 2) // 6
    else:
        raise NotImplementedError("NIE")


# 再帰呼出し
def rec(i, k, smaller):
    if i == N:
        return 1 if k == 0 else 0
    if k == 0:
        return 1
    if smaller:
        # 残っている桁数からk個を選び，それぞれ9^kのパターンがある
        return com(N - i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i + 1, k , False)
        else:
            zero = rec(i + 1, k, True)
            aida = rec(i + 1, k - 1, True) * (int(S[i]) - 1)
            ichi = rec(i + 1, k - 1, False)
            return zero + aida + ichi

ans = rec(0, K, False)
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# DPの対象配列の先頭に0を追加(先頭を0桁目、でなく1桁目、として可読性を上げる)
# さらに、入力を1文字ずつ分けて、数値型でリストに格納する。
def get_dp_target(string: str) -> []:
    return [0] + list(map(int, list(string)))


# 実装を行う関数
def resolve(test_def_name=""):
    try:
        # ※DP対象は以下の関数で取得※
        n = get_dp_target(input())

        target = int(input())

        # ---------------------------------
        # DP準備
        # ---------------------------------
        # DP配列作成※問題ごとに変える※
        dp = [[[0 for _ in range(101)] for _ in range(2)] for _ in range(len(n) + 1)]

        # DP準備(1桁目の設定)※0も処理するので1桁目の値+1回ループ
        for i in range(n[1] + 1):
            # 未満フラグ設定
            is_smaller = True if i < n[1] else False
            # ※問題ごとに変える※
            # dp[1][is_smaller][?] = ? というイメージは同じ。
            not_zero_count = 0 if i == 0 else 1
            dp[1][is_smaller][not_zero_count] += 1

        # ---------------------------------
        # DP(2桁目以降を処理する) ※ポイント：各ループの回数はDP配列の要素数と同じ。
        for place in range(2, len(n)):

            # 未満フラグの全パターンループ(2種類しかないが・・)
            for is_smaller in range(2):

                # 0以外の出現回数ループ(DPの兼ね合い上、範囲は0~100でOK)
                for not_zero_count in range(100):
                    # 値ループ
                    val_range = 10 if is_smaller else n[place] + 1
                    for val in range(val_range):
                        # 値によるフラグ変動
                        work_is_smaller = is_smaller or val < n[place]
                        work_not_zero_count = not_zero_count if val == 0 else not_zero_count + 1
                        dp[place][work_is_smaller][work_not_zero_count] += dp[place - 1][is_smaller][not_zero_count]

        print(dp[len(n) - 1][0][target] + dp[len(n) - 1][1][target])
    except IndexError as err:
        print("インデックスエラー:", err.args[0])


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """100
1"""
        output = """19"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """25
2"""
        output = """14"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """314159
2"""
        output = """937"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3"""
        output = """117879300"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original(self):
        pass


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

for i in range(len(N)):
    for k in range(K+1):
        dp[i+1][0][k] += dp[i][0][k]
        dp[i+1][0][k+1] += dp[i][0][k]*9

        if N[i] != "0":
            dp[i+1][0][k] += dp[i][1][k]
            dp[i+1][0][k+1] += dp[i][1][k]*(int(N[i])-1)
            dp[i+1][1][k+1] += dp[i][1][k]
        else:
            dp[i+1][1][k] += dp[i][1][k]

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

Submission status: Accepted

Solution code:
import math


def comb(n, r):
    if n < r or r < 0:
        return 0
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume *= (n - i + 1)
        deno *= (i)
    return nume//deno


def solve(N, K):
    if N < K:
        return 0
    if K == 0:
        return 1
    keta = math.floor(math.log(N, 10)) + 1
    x = N//pow(10, keta-1)
    ret = 0
    if K > keta:
        return 0
    # ptn1: 最大の桁は0
    if keta != K:
        ret += comb(keta - 1, K) * (9 ** K)
    # ptn2: 最大の桁はNのその桁の値未満
    ret += (x-1)*comb(keta-1, K-1)*pow(9, K-1)
    # ptn3: 最大の桁はNのその桁の値
    ret += solve(N % pow(10, keta-1), K - 1)
    return ret


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

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
k = INT()

@lru_cache(None)
def F(n, k):
    # n以下で0でないものがちょうどk個ある数字の個数
    if n < 10:
        if k == 0:
            return 1
        if k == 1:
            return n
        return 0
    q, r = divmod(n, 10)
    ret = 0
    if k >= 1:
        ret += F(q, k-1) * r
        ret += F(q-1, k-1) * (9-r)
    ret += F(q, k)
    return ret

print(F(n, k))

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
k = INT()

@lru_cache(None)
def F(n, k):
    # n以下で0でないものがちょうどk個ある数字の個数
    if n < 10:
        if k == 0:
            return 1
        if k == 1:
            return n
        return 0
    q, r = divmod(n, 10)
    ret = 0
    if k >= 1:
        # 1の位が0
        ret += F(q, k-1) * r
        ret += F(q-1, k-1) * (9-r)
    ret += F(q, k)
    return ret

print(F(n, k))

Submission status: Accepted

Solution code:
import bisect, collections, copy, functools, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    K = I()

    # [0, N]で、non0の数字がK個あるものの数
    @functools.lru_cache
    def f(N, K):
        if N == K == 0:
            ret = 1
        elif N > 0 and K >= 0:
            ret = f(N // 10, K) + N % 10 * f(N // 10, K - 1) + (9 - N % 10) * f(N // 10 - 1, K - 1)
        else:
            ret = 0
        return ret
    
    ans = f(N, K)
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve(n, k, m):
    ans = 0
    for i in range(k, m):
        # i: 桁数
        if k == 1:
            ans += 9
        else:
            ans += pow(9, k)*comb(i-1, k-1)
    if k == 1:
        ans += int(n[0])
    elif k == 2:
        ans += (int(n[0])-1)*pow(9, k-1)*comb(m-1, k-1)
        j = 1
        while j < m and n[j] == '0':
            j += 1
        if j < m:
            ans += int(n[j]) + pow(9, k-1)*comb(m-1-j, k-1)
    else:
        while m >= k and n.count('0') > m - k:
            n = str(int(n)-1)

        if m > len(n):
            print(ans)
            return ans

        m = len(n)
        a = []
        for i in range(m):
            if len(a) < 3 and n[i] != '0':
                a.append(i)

        if len(a) == 3:
            ans += 1 + int(n[a[2]])-1 + 9*comb(m-1-a[2], 1)
            ans += (int(n[a[1]])-1)*9*comb(m-1-a[1], 1) + 9*9*comb(m-1-a[1], 2)
            ans += (int(n[a[0]])-1)*9*9*comb(m-1-a[0], 2)
    print(ans)
    return ans

def solve2(n, k, m):
    ans = 0
    for i in range(1, int(n)+1):
        if len(str(i)) - str(i).count('0') == k:
            ans += 1
    print(ans)
    return ans

if __name__ == '__main__':
    n = input()
    k = INT()
    m = len(n)

    solve(n,k,m)
    #solve2(n,k,m)
    #for i in range(10000):
    #    print(i)
    #    if solve(str(i), k, len(str(i))) != solve2(str(i), k, len(str(i))):
    #        break

Submission status: Accepted

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


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


for i in range(len(n)):
  x=int(n[i])
  for j in range(k+1):
    
    if x==0:
      dp[i+1][j][0]+=dp[i][j][0]
    else:
      dp[i+1][j+1][0]+=dp[i][j][0]

    dp[i+1][j][1]+=dp[i][j][1]    #０
    if x!=0:
      dp[i+1][j][1]+=dp[i][j][0]    #０
    
    dp[i+1][j+1][1]+=dp[i][j][1]*9    #1~9

    if x!=0:
      dp[i+1][j+1][1]+=dp[i][j][0]*max(x-1,0)    #1~x-1


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

Submission status: Accepted

Solution code:
n=[int(x) for x in list(input())]
l=len(n)
k=int(input())
"""
桁DP
桁数,0でないcount,ギリギリflagでdp
"""
dp = [[[0 for _ in range(2)] for _ in range(k+1)] for _ in range(l+1)]
#n[0]は0ではない
dp[1][0][0] = 1
dp[1][1][0] = n[0] - 1
dp[1][1][1] = 1
for i in range(2,l+1):
  for j in range(0,min(i,k)+1):
    if j > 0:
      dp[i][j][1] += dp[i-1][j-1][1]*(n[i-1]>0)
      dp[i][j][0] += dp[i-1][j-1][0]*9+dp[i-1][j-1][1]*max(0,n[i-1]-1)
    dp[i][j][1] += dp[i-1][j][1]*(n[i-1]==0)
    dp[i][j][0] += dp[i-1][j][0] + dp[i-1][j][1]*(n[i-1]>0)
    #print(i,j,dp[i][j])
print(sum(dp[l][k]))

Submission status: Accepted

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

l=len(n)

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

for i,dig in enumerate(n):
    dig=int(dig)

    for j in range(10):
        for k in range(100):
            nk=k if j==0 else k+1
            if j<dig:
                dp[i+1][nk][1]+=dp[i][k][0]+dp[i][k][1]
            elif j==dig:
                dp[i+1][nk][1]+=dp[i][k][1]
                dp[i+1][nk][0]+=dp[i][k][0]
            else:
                dp[i+1][nk][1]+=dp[i][k][1]

print(dp[l][kk][0]+dp[l][kk][1])

Submission status: Accepted

Solution code:
"""
桁DPで解ける
dp[i][j][k][l] => i桁目まで見る。i桁目がjであるような数字の数。kは0でない数の個数のメモ。lは未満フラグ。
"""
N = input()
K = int(input())
dp = [[[[0]*(2) for _ in range(5)]for _ in range(10)]for _ in range(len(N))]

#初期化
x = int(N[0])
for i in range(x+1):
    if i == 0:
        dp[0][i][0][1] += 1
    else:
        if i<x:
            flag = 1
        else:
            flag = 0
        dp[0][i][1][flag] += 1

for i in range(len(N)-1):
    x = int(N[i+1])
    for j in range(10):
        for k in range(4):
            for l in range(2):
                if l:
                    r = 10
                else:
                    r = x+1
                for m in range(r):
                    if l==0 and m==x:
                        flag = 0
                    else:
                        flag = 1
                    
                    if m == 0:
                        cnt = k
                    else:
                        cnt = k+1
                    dp[i+1][m][cnt][flag] += dp[i][j][k][l]

ans = 0
for j in range(10):
    ans += sum(dp[-1][j][K])

print(ans)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    dp[lower][i][j] - if number of ways such that one of the digit is lower and contains j non-zero digits
    """
    N = input()
    length = len(N)
    K = read_int()
    dp = [
        [[0 for _ in range(K+1)] for _ in range(length+1)]
        for _ in range(2)
    ]
    dp[False][0][0] = 1
    for i in range(1, length+1):
        dp[True][i][0] = 1
        for j in range(1, K+1):
            dp[True][i][j] = 9*dp[True][i-1][j-1]+dp[True][i-1][j]
            if int(N[i-1]) > 0:
                dp[True][i][j] += dp[False][i-1][j-1]*(int(N[i-1])-1)+dp[False][i-1][j]
                dp[False][i][j] = dp[False][i-1][j-1]
            else:
                dp[False][i][j] = dp[False][i-1][j]
    return dp[True][length][K]+dp[False][length][K]


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10**9)


def comb(n, r):  # 普通のcombination計算
    if r < 0 or r > n:
        return 0
    else:
        n1 = math.factorial(n)
        n21 = math.factorial(n - r)
        n22 = math.factorial(r)
        ans = n1 // (n21 * n22)
        return ans


"""
solve(i, k, smaller)
:= i桁目以降について、0以外の値を残りk個使用可能という状況を考える。
このときi桁目までの部分が「等しい」か「strictに小さくなっている」かを
smallerフラグによって分岐する。
"""


def solve(i, k, smaller):  # 再帰

    # print(i, k, smaller)

    if i == N:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    if smaller == True:
        return comb(N - i, k) * pow(9, k)

    else:
        if S[i] == "0":
            return solve(i + 1, k, False)
        else:
            """
            ex. S = 314159　の場合
            000000〜099999 := a
            100000〜299999 := b
            300000〜314159 := c　のように場合分け
            """
            a = solve(i + 1, k, True)
            b = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
            c = solve(i + 1, k - 1, False)
            return a + b + c


# 問題文ではNだが、文字列として扱うのでSと名付ける
S = input()
# Sの桁数、問題文のNとは違う
N = len(S)
K = int(input())

ans = solve(0, K, False)
print(ans)

Submission status: Accepted

Solution code:
def zeroTrim(s):
    while s[0] == '0':
        if len(s) == 1:
            break
        s = s[1:]
    return s

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

def calc(N, K):
    digit = len(N)
    res = 0

    if K == 1:
        if digit > 1:
            res += (digit - 1) * 9
        res += int(N[0])
    elif K == 2:
        if digit <= 1:
            return 0
        if digit > 2:
            res += 9 * 9 * (digit - 1) * (digit - 2) // 2
        for i in range(int(N[0])-1):
            res += calc('9'*(digit-1), 1)
        res += calc(zeroTrim(N[1:]), 1)
    else:
        if digit <= 2:
            return 0
        if digit > 3:
            res += 9 * 9 * 9 * (digit - 1) * (digit - 2) * (digit - 3) // 6
        
        for i in range(int(N[0])-1):
            res += calc('9'*(digit-1), 2)
        res += calc(zeroTrim(N[1:]), 2)
    return res

print(calc(N, K))

Submission status: Accepted

Solution code:
s=input()
m=int(input())
n=len(s)
if n==1:
  print([0,int(s)][m==1])
  exit()
dp=[[[0]*2 for _ in range(m+1)] for _ in range(n)]
dp[0][0][1]=1
dp[0][1][1]=int(s[0])-1
dp[0][1][0]=1
for i in range(1,n):
  for j in range(m+1):
    if j:
      dp[i][j][1]+=9*dp[i-1][j-1][1]
      if s[i]!='0':
        dp[i][j][0]+=dp[i-1][j-1][0]
        dp[i][j][1]+=(int(s[i])-1)*dp[i-1][j-1][0]
    if s[i]=='0':dp[i][j][0]+=dp[i-1][j][0]
    dp[i][j][1]+=dp[i-1][j][1]
    if s[i]!='0':dp[i][j][1]+=dp[i-1][j][0]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:
import math

#-桁dpなる書き方に挑戦-#
#-dp[k][j][i] 先頭からi桁目まで決めたときに,
    #- 0でない要素をj個使っていて、k=0 小さいことが確定していない , k=1 確定

def solve(sN):
    dp = [[[0]*105 for _ in range(4)] for _ in range(2) ] #余分に取っておく。あとでlen(N)の要素を取り出し
    #初期条件
    dp[0][0][0]=1 #なにも決めていな状態。空集合。一致
    for i in range(len(sN)):
        for j in range(4):
            for k in range(2):
                nd = int(sN[i])#sNの今の桁をnd。これから決める桁数字をdとする
                for d in range(10):
                    ni = i+1;nj=j;nk=k
                    if d != 0: #dが0でないならnjを１つ足す
                        nj +=1
                    if nj > K:#使える0以外の数字の個数を超えていたらだめ
                        continue
                    if k ==0:#これまでの桁が一致している。
                        if d > nd:#数字が超えるからだめ
                            continue
                        if d < nd:#小さいなら、以降小さくなることが確定
                            nk = 1
                    dp[nk][nj][ni]+=dp[k][j][i]
    ans = dp[0][K][len(sN)]+dp[1][K][len(sN)]#小さいものが確定＆一致
    return ans

sN = input()
K = int(input())
lenN = len(sN)
ans = solve(sN)
print(ans)

Submission status: Accepted

Solution code:
import math
def isMore(N,K):#- N以上の数で、０でないのが丁度K個
    #-len(N)よりもKがおおきかったら0 埋められない
    if len(N) < K:
        return 0
    #最高位の数字を1つ繰り上げれば、なんでも大きい。ただし、Kは1以上
    if K>=1:
        tmp = (9-int(N[0]))*fact[len(N)-1]//((fact[len(N)-K])*(fact[K-1]))*(9**(K-1))
        #一桁ならtmpを返す
        if len(N)==1:
            return tmp
        #２桁以上あるなら＆最高位が０なら、最高桁繰り上げ＋最高桁同じ＋０でないものがK個
        elif len(N)>1 and N[0]=='0':
            return tmp + isMore(N[1:],K)
        #２桁以上あるなら＆最高位が０以外なら、最高桁繰り上げ＋最高桁同じ＋０でないものがK-1個
        elif len(N)>1 and N[0]!='0':
            return tmp + isMore(N[1:],K-1)
    #Kが0ならどうやってもNより大きいものが作れない0
    if K == 0:
        return 0

N = input()
K = int(input())
lenN = len(N)
fact = [1]*101
for i in range(1,101):
    fact[i] = fact[i-1]*i

ans = fact[lenN]//((fact[lenN-K])*fact[K])*(9**K)
ans -= isMore(N,K)
print(ans)

Submission status: Accepted

Solution code:
import math
def isMore(N,K):#- N以上の数で、０でないのが丁度K個
    #-len(N)よりもKがおおきかったら0
    if len(N) < K:
        return 0
    #最高位の数字を1つ繰り上げれば、なんでも大きい。ただし、Kは1以上
    if K>=1:
        tmp = (9-int(N[0]))*fact[len(N)-1]//((fact[len(N)-K])*(fact[K-1]))*(9**(K-1))
        if len(N)==1:
            return tmp
        elif len(N)>1 and N[0]=='0':
            return tmp + isMore(N[1:],K)
        elif len(N)>1 and N[0]!='0':
            return tmp + isMore(N[1:],K-1)
    if K == 0:
        return 0

N = input()
K = int(input())
lenN = len(N)
fact = [1]*101
for i in range(1,101):
    fact[i] = fact[i-1]*i

ans = fact[lenN]//((fact[lenN-K])*fact[K])*(9**K)
ans -= isMore(N,K)
print(ans)

Submission status: Accepted

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

def f(dig, under, num):
  if num > l - dig: return 0
  if num == 0: return 1
  if dig == l-1:
    if under: return int(n[dig])
    else: return 9
  if under:
    if n[dig] == '0':
      res = f(dig+1, True, num)
      #print(dig, under, num, res, 'aaa')
      return res
    else:
      res = f(dig+1, False, num)
      if int(n[dig]) > 1:
        res += (int(n[dig])-1) * f(dig+1, False, num-1)
      res += f(dig+1, True, num-1)
      #print(dig, under, num, res, 'bbb')
      return res
  else:
    res = f(dig+1, False, num)
    res += 9 * f(dig+1, False, num-1)
    #print(dig, under, num, res, 'ccc')
    return res

ans = f(0, True, k)
print(ans)

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=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(score)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def solve(N, K, L):
    dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(L + 1)]
    dp[0][0][0] = 1
    for i in range(L):
        D = N[i]
        for j in range(2):
            d_max = 9 if j == 1 else D
            for k in range(K + 1):
                if k < K:
                    for d in range(d_max + 1):
                        dp[i + 1][int(j or (d < D))][k + int(d > 0)] += dp[i][j][k]
                else:
                    dp[i + 1][j][k] += dp[i][j][k]

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


def main():
    N = list(map(int, input().rstrip()))
    K = int(input())

    L = len(N)
    ans = solve(N, K, L)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

# import numba as nb
import numpy as np

input = sys.stdin.readline


# @nb.njit("i8(i8[:],i8,i8)", cache=True)
def solve(N, K, L):
    dp = np.zeros(shape=(L + 1, 2, K + 1), dtype=np.int64)
    dp[0][0][0] = 1
    for i in range(L):
        D = N[i]
        for j in range(2):
            d_max = 9 if j == 1 else D
            for k in range(K + 1):
                if k < K:
                    for d in range(d_max + 1):
                        dp[i + 1][int(j or (d < D))][k + int(d > 0)] += dp[i][j][k]
                else:
                    dp[i + 1][j][k] += dp[i][j][k]

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


def main():
    N = np.array(list(input().rstrip()), dtype=np.int64)
    K = int(input())

    L = N.shape[0]
    ans = solve(N, K, L)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def solve_K_1(N):
    S = str(N)
    d = len(S)
    return 9 * (d - 1) + int(S[0])


def solve_K_2(N):
    if N <= 99:
        return N - solve_K_1(N)
    S = str(N)
    d = len(S)
    res = 0
    res += 81 * (d - 1) * (d - 2) // 2
    res += 9 * (d - 1) * (int(S[0]) - 1)
    x = 0
    for i in range(1, d):
        if S[i] != "0":
            x = int(S[i])
            break
    i += 1
    res += x + 9 * (d - i)
    return res


def solve_K_3(N):
    if N <= 999:
        return N - solve_K_1(N) - solve_K_2(N)
    S = str(N)
    d = len(S)
    res = 0
    for n in range(3, d):
        res += 729 * (n - 1) * (n - 2) // 2
    res += 81 * (d - 1) * (d - 2) // 2 * (int(S[0]) - 1)
    res += solve_K_2(int(S[1:]))
    return res


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

    if K == 1:
        ans = solve_K_1(N)
    elif K == 2:
        ans = solve_K_2(N)
    elif K == 3:
        ans = solve_K_3(N)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

from functools import lru_cache

N = int(sys.stdin.readline().rstrip())
K = int(sys.stdin.readline().rstrip())


@lru_cache(None)
def F(N, K):
    """(0以上）N以下で、0でないものがちょうどK個"""

    assert N >= 0  # Nが非負であることを保証する

    if N < 10:  # N が一桁
        if K == 0:  # 使える 0 以外の数がない場合
            return 1  #
        if K == 1:
            return N  # 1,2,...,N までのどれか
        return 0  # それ以上 K が余っていたら作れない

    q, r = divmod(N, 10)  # N = 10*q + r と置く

    ret = 0
    if K >= 1:
        # 1の位(r)が nonzero
        ret += F(q, K - 1) * r  #
        ret += F(q - 1, K - 1) * (9 - r)

    # 1の位(r)が zero
    ret += F(q, K)
    return ret


print(F(N, K))