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:
N=input()
K=int(input())
dp_0 = [[0]*(len(N)) for i in range(K+1)]
dp_1 = [[0]*(len(N)) for i in range(K+1)]
dp_0[0][0]=1
dp_0[1][0]=int(N[0])-1
dp_1[1][0]=1
for i in range(len(N)-1):
    for j in range(K+1):
        if j==K:
            dp_0[j][i+1] += dp_0[j][i]
        elif j==0:
            dp_0[j][i+1] =dp_0[j][i]
            dp_0[j+1][i+1] += dp_0[j][i]*9
        else:
            dp_0[j][i+1] += dp_0[j][i]
            dp_0[j+1][i+1] += dp_0[j][i]*9
        if j != K and N[i+1] != '0':
            dp_0[j+1][i+1] += (int(N[i+1])-1)*dp_1[j][i]
            dp_0[j][i+1] += dp_1[j][i]
            dp_1[j+1][i+1] = dp_1[j][i]
        elif N[i+1] =='0':
            dp_1[j][i+1] = dp_1[j][i]
        else:

            dp_0[j][i+1] += dp_1[j][i]

print(dp_0[K][len(N)-1]+dp_1[K][len(N)-1])

Submission status: Accepted

Solution code:
sn = input()
k = int(input())
d = len(sn)

dp1 = [[0 for j in range(k + 1)] for i in range(d + 1)] # 未満
dp2 = [[0 for j in range(k + 1)] for i in range(d + 1)] # 未確定
dp2[0][0] = 1
for i in range(d):
    for j in range(k):
        if sn[i] == '0':
            dp2[i + 1][j] += dp2[i][j]
        else:
            dp2[i + 1][j + 1] += dp2[i][j] # i桁目が1以上で同じ場合
            dp1[i + 1][j + 1] += (int(sn[i]) - 1) * dp2[i][j] # i桁目が1以上N[i]未満の場合
            dp1[i + 1][j] += dp2[i][j] # i桁目が0の場合

        dp1[i + 1][j] += dp1[i][j]
        dp1[i + 1][j + 1] += dp1[i][j] * 9
    dp1[i + 1][k] += dp1[i][k]
    dp2[i + 1][k] += dp2[i][k]
print(dp1[-1][-1] + dp2[-1][-1])

Submission status: Accepted

Solution code:
import numpy as np

n = input()
k = int(input()) + 1
d = len(n)
dp0 = np.zeros((d, k), dtype=int)
dp1 = np.zeros((d, k), dtype=int)
dp0[0][0] = 1
dp0[0][1] = int(n[0]) - 1
dp1[0][1] = 1
for i in range(d - 1):
    for j in range(k):
        dp0[i + 1][j] = dp0[i][j]
        if j > 0:
            dp0[i + 1][j] += 9 * dp0[i][j - 1]
        m = int(n[i + 1])
        if m > 0:
            dp0[i + 1][j] += dp1[i][j]
            if j > 0:
                dp0[i + 1][j] += (m - 1) * dp1[i][j - 1]
                dp1[i + 1][j] = dp1[i][j - 1]
            else:
                dp1[i + 1][j] = 0
        else:
            dp1[i + 1][j] = dp1[i][j]
print(dp0[d - 1][k - 1] + dp1[d - 1][k - 1])

Submission status: Accepted

Solution code:
from math import factorial
N = int(input())
K = int(input())
strN = str(N)
lenN = len(strN)
#dp[i][j][k] をi:今何桁目を調べているか、j:未満フラグ、k:何個0以外を出したか、としてdpしたい
dp = [[[0]*(K+1) for i in range(2)] for j in range(lenN+1)]
dp[0][0][0] = 1
for i in range(lenN):
    for j in range(2):
        for k in range(K+1):
            if j == 0:
                if k != K:
                    if strN[i] == "0":
                        dp[i+1][j][k] += dp[i][j][k]
                    else:
                        dp[i+1][j][k+1] +=  dp[i][j][k]
                        dp[i+1][1][k+1] +=  (int(strN[i])-1) * dp[i][j][k]
                        dp[i+1][1][k] += dp[i][j][k]
                else:
                    dp[i+1][j][k] += dp[i][j][k]
            if j == 1:
                if k != K:
                    dp[i+1][j][k+1] += 9*dp[i][j][k]
                    dp[i+1][j][k] += dp[i][j][k]
                else:
                    dp[i+1][j][k] += dp[i][j][k]
print(dp[lenN][0][K] + dp[lenN][1][K])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
 
dp = [[0] * (k + 2) for _ in range(2)]
dp[0][0] = 1
 
for d in n:
    ndp = [[0] * (k + 2) for _ in range(2)]
    for i in range(k + 1):
        ndp[1][i] += dp[1][i]
        ndp[1][i + 1] += dp[1][i] * 9
        if d == '0':
            ndp[0][i] += dp[0][i]
        else:
            ndp[1][i] += dp[0][i]
            ndp[1][i + 1] += dp[0][i] * (int(d) - 1)
            ndp[0][i + 1] += dp[0][i]
    dp = ndp
print(dp[0][k] + dp[1][k])

Submission status: Accepted

Solution code:
N=input()
K=int(input())
S="0"*(100-len(N))+N
DP=[[[0]*2 for _ in range(K+2)] for _ in range(101)]

DP[0][0][0] = 1
for i in range(100):
  for j in range(K+1):
    #SがN以下かわからないまま、「0」の文字をなぞるとき、0でない数字jはそのまま
    if S[i]=='0':
      DP[i+1][j][0]+=DP[i][j][0]
      
    #SがN以下かわからないまま、「0」以外の文字をなぞるとき、0でない数字jも+1
    else:
      DP[i+1][j+1][0]+=DP[i][j][0]
    
    #SがN以下が確定している　
    DP[i+1][j][1]+=sum(DP[i][j])
    if int(S[i])==0:
      #あとは数字が同じとはいえ000…と埋めるしかないパターン
      DP[i+1][j][1]-=DP[i][j][0]
      
    #SがN以下が確定しているものは、1~9をくっつけたものと、同じ桁だけどより低い数字が来たとき
    DP[i+1][j+1][1] += DP[i][j][1]*9+DP[i][j][0]*(max(0, int(S[i])-1))
    
print(DP[-1][K][0]+DP[-1][K][1])

Submission status: Accepted

Solution code:
N = input()
n = len(N)
K = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(N[i])
a.insert(0,0)
dp = [[[0,0,0,0],[0,0,0,0]] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(1,n+1):
    for f in range(2):
        if f == 0:
            for k in range(4):
                if a[i] != 0:
                    if k !=0:
                        dp[i][0][k] = dp[i-1][0][k-1]
                    dp[i][1][k] += dp[i-1][0][k]
                    if k == 3:
                        continue
                    dp[i][1][k+1] += dp[i-1][0][k] * (a[i] - 1)
                if a[i] == 0:
                    dp[i][0][k] = dp[i-1][0][k]
        if f == 1:
            for k in range(4):
                if k!=0:
                    dp[i][1][k] += dp[i-1][1][k] + dp[i-1][1][k-1] * 9
                if k == 0:
                    dp[i][1][k] += dp[i-1][1][k]
ans = dp[n][0][K] + dp[n][1][K]
print(ans)

Submission status: Accepted

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

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

for d in range(int(N[0])+1):
    DP[0][d<int(N[0])][d!=0] += 1

for i in range(len(N)-1):
    for j in range(2):
        for k in range(K+1):
            for d in range(10 if j else int(N[i+1])+1):
                if k+(d!=0) <= K:
                    DP[i+1][j|(d<int(N[i+1]))][k+(d!=0)] += DP[i][j][k]

print(DP[len(N)-1][0][K]+DP[len(N)-1][1][K])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
#nより小さいことが確定しているdp
#dp_0[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数
dp_0 = [[0 for i in range(k+1)] for j in range(len(n))]
#nより小さいことが確定していないdp
#dp_1[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数。
dp_1 = [[0 for i in range(k+1)] for j in range(len(n))]
dp_0[0][0] = 1
dp_0[0][1] = int(n[0]) - 1
dp_1[0][1] = 1
for i in range(1,len(n)):
    dp_0[i][0] = 1
    for j in range(1,k+1):
    #今回の桁が0でないことを想定
        if n[i] != '0':
            #0を使う場合と使わない場合両方考える
            #まずは使わない場合
            dp_0[i][j] += dp_0[i-1][j-1] * 9 + dp_1[i-1][j-1] * (int(n[i]) - 1)
            dp_1[i][j] += dp_1[i-1][j-1]
            #0を使う場合。この時はjが変化しない。なぜなら0を使うか
            #dp_1の更新は無し。
            #なぜなら、今回の桁が0でないことを想定しているため、もうnを超えることはないから
            dp_0[i][j] += dp_0[i-1][j] + dp_1[i-1][j]
        else:
            #今回の桁が0の場合 
            #dp_1を遷移式に入れない理由は、今回の桁が0だった時は、どんな数字の選び方をしても
            #さっきの桁まででnより小さいことが確定しないものが
            #今回の桁の決め方で確定することはないから。
            dp_0[i][j] = dp_0[i-1][j-1] * 9 + dp_0[i-1][j]
            dp_1[i][j] = dp_1[i-1][j]
print(dp_0[-1][k] + dp_1[-1][k])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
#nより小さいことが確定しているdp
#dp_0[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数
dp_0 = [[0 for i in range(k+1)] for j in range(len(n))]
#nより小さいことが確定していないdp
#dp_1[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数。
dp_1 = [[0 for i in range(k+1)] for j in range(len(n))]
dp_0[0][0] = 1
dp_0[0][1] = int(n[0]) - 1
dp_1[0][1] = 1
for i in range(1,len(n)):
    dp_0[i][0] = 1
    for j in range(1,k+1):
    #今回の桁が0でないことを想定
        if n[i] != '0':
            #0を使う場合と使わない場合両方考える
            #まずは使わない場合
            dp_0[i][j] = dp_0[i-1][j-1] * 9 + dp_1[i-1][j-1] * (int(n[i]) - 1) + dp_0[i-1][j] + dp_1[i-1][j]
            dp_1[i][j] = dp_1[i-1][j-1]
            #0を使う場合。この時はjが変化しない。なぜなら0を使うか
            #dp_1の更新は無し。
            #なぜなら、今回の桁が0でないことを想定しているため、もうnを超えることはないから
        else:
            #今回の桁が0の場合 
            #dp_1を遷移式に入れない理由は、今回の桁が0だった時は、どんな数字の選び方をしても
            #さっきの桁まででnより小さいことが確定しないものが
            #今回の桁の決め方で確定することはないから。
            dp_0[i][j] = dp_0[i-1][j-1] * 9 + dp_0[i-1][j]
            dp_1[i][j] = dp_1[i-1][j]
#print(dp_0)
#print(dp_1)
print(dp_0[-1][k] + dp_1[-1][k])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from functools import lru_cache
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


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


@lru_cache(None)
def rec(i, k, smaller):
    if k == 0:
        return 1
    if n - i < k:
        return 0

    if smaller:
        # i桁目がNより小さいとき
        return cmb(n - i, k) * pow(9, k)
    else:
        if N[i] == 0:
            return rec(i + 1, k, False)
        else:
            a = rec(i + 1, k, True)
            b = rec(i + 1, k - 1, True) * (N[i] - 1)
            c = rec(i + 1, k - 1, False)
            return a + b + c


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

Submission status: Accepted

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

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

    print(tmp(n, k))

def tmp(x, k):
    # k が 桁数以上の場合、パターンなし
    if len(x) < k:
        return 0
    # k が 0 の場合、全て 0 の 1パターン
    if k <= 0:
        return 1
    if len(x) == k == 1:
        return int(x)
    else:
        int_x = list(map(int, list(x)))
        next_x = str(int(x[1:]))

        # 最大桁を k の 1つとする場合、最大値の場合と それ以外の場合で計算が異なる。
        a = tmp(next_x, k-1)
        # 最大値, 0 以外の場合は、以下の桁は全ての値を取り得る
        b = (int_x[0]-1) * pow(9, k-1) * combination(len(x)-1, k-1)
        # 最大桁を k の 1つとしない場合（最大桁を0とみなす）
        c = pow(9, k) * combination(len(x)-1, k)

        return a + b + c

def combination(n, k):
    m = 1
    l = 1
    for i in range(n, n-k, -1):
        m = m * i

    for j in range(k, 0, -1):
        l = l * j
    
    return int(m / l)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


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


@lru_cache(None)
def rec(i, k, yn):
    if k == 0:
        return 1
    elif i == n:
        return 0
    if n - i < k:
        return 0

    if yn:
        # i桁目がNより小さいとき
        return cmb(n - i, k) * pow(9, k)
    else:
        if N[i] == 0:
            return rec(i + 1, k, False)
        else:
            a = rec(i + 1, k, True)
            b = rec(i + 1, k - 1, True) * (N[i] - 1)
            c = rec(i + 1, k - 1, False)
            return a + b + c


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

Submission status: Accepted

Solution code:
N = input()
K = int(input())
N = "0" + N
K = int(K)

L = len(N)

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

for i in range(1, L):
    d = int(N[i])
    # 境界
    for k in range(0, K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if d != 0:
            dp[i][1][k] += dp[i - 1][0][k]

    for k in range(1, K + 1):
        dp[i][1][k] += dp[i - 1][1][k - 1] * 9
        if d != 0:
            dp[i][1][k] += dp[i - 1][0][k - 1] * (d - 1)
            dp[i][0][k] += dp[i - 1][0][k - 1]
        else:
            dp[i][0][k] += dp[i - 1][0][k]

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

Submission status: Accepted

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

def main():
    N = str(input())
    K = int(input())
    
    l = len(N)
    dpa = [[0 for _ in range(K+1)] for _ in range(l)]
    dpb = [[0 for _ in range(K+1)] for _ in range(l)]
    
    dpa[0][0],dpa[0][1],dpb[0][1] = 1,int(N[0])-1,1
    for i in range(1,l):
        dpa[i][0] = 1
        num = int(N[i])
        if num == 0:
            for j in range(K):
                j += 1
                dpa[i][j] = dpa[i-1][j-1]*9 + dpa[i-1][j]
                dpb[i][j] = dpb[i-1][j]
        else:
            for j in range(K):
                j += 1
                dpa[i][j] = dpa[i-1][j-1]*9 + dpa[i-1][j] + dpb[i-1][j-1]*(num-1) + dpb[i-1][j]
                dpb[i][j] = dpb[i-1][j-1]

    print(dpa[l-1][K]+dpb[l-1][K])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N = str(input())
    K = int(input())
    
    l = len(N)
    dpa = [[0 for _ in range(K+1)] for _ in range(l)]
    dpb = copy.deepcopy(dpa)
    
    dpa[0][0],dpa[0][1],dpb[0][1] = 1,int(N[0])-1,1
    for i in range(1,l):
        dpa[i][0] = 1
        num = int(N[i])
        if num == 0:
            for j in range(K):
                j += 1
                dpa[i][j] = dpa[i-1][j-1]*9 + dpa[i-1][j]
                dpb[i][j] = dpb[i-1][j]
        else:
            for j in range(K):
                j += 1
                dpa[i][j] = dpa[i-1][j-1]*9 + dpa[i-1][j] + dpb[i-1][j-1]*(num-1) + dpb[i-1][j]
                dpb[i][j] = dpb[i-1][j-1]

    print(dpa[l-1][K]+dpb[l-1][K])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

n = len(s)

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

Submission status: Accepted

Solution code:
import itertools
import sys
import numpy as np
from collections import deque
from itertools import combinations
from functools import lru_cache
sys.setrecursionlimit(10**9)

@lru_cache(None)
def solve(N,K):
    # print(N,K)
    if N <= 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0

    if K < 0 or len(str(N)) < K:
        return 0

    ans = 0
    m, last = divmod(N,10)
    ans += solve(m,K-1) * last + solve(m-1,K-1) * (9 - last) + solve(m,K)

    return ans


def main():
    N,K = map(int,[input(),input()])

    print(solve(N,K))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500)


def calc(N, K):
    if len(N) < K or K <= 0:
        return 0
    tmp = 9 - int(N[0])
    for i in range(K-1):
        tmp *= 9 * (len(N) - 1 - i)
    for i in range(K-1):
        tmp //= (i+1)
    if N[0] != "0":
        return tmp + calc(N[1:], K-1)
    else:
        return tmp + calc(N[1:], K)


def main():
    N = input()
    K = int(input())
    if len(N) < K:
        print(0)
        return
    ans = 1
    for i in range(K):
        ans *= 9 * (len(N) - i)
    for i in range(K):
        ans //= (i+1)
    ans -= calc(N, K)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
def permutations_count(n, r):
    if not n>=r>=0:
        return(0)
    else:
        return factorial(n) // factorial(n - r)
def combinations_count(n, r):
    if not n>=r>=0 or n<0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())
length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if K-count3 >=1:count+=combinations_count(length-1-i,K-count3)*(9**(K-count3))
        if K-count3-1 >=0:count+=combinations_count(length-1-i,K-count3-1)*(9**(K-1-count3))*(int(N[i])-1)
        count3+=1
    if K-count3==0:
        count+=1
        #count+=int(N[i])
        break
print(count)

Submission status: Accepted

Solution code:
N=input()
K=int(input())
S="0"*(100-len(N))+N
DP=[[[0]*2 for _ in range(K+2)] for _ in range(101)]

DP[0][0][0] = 1
for i in range(100):
  for j in range(K+1):
    #SがN以下かわからないまま、「0」の文字をなぞるとき、0でない数字jはそのまま
    if S[i]=='0':
      DP[i+1][j][0]+=DP[i][j][0]
      
    #SがN以下かわからないまま、「0」以外の文字をなぞるとき、0でない数字jも+1
    else:
      DP[i+1][j+1][0]+=DP[i][j][0]
    
    #SがN以下が確定している　
    DP[i+1][j][1]+= DP[i][j][1]
    if int(S[i])>0:
      #0以外の文字がくると、
      DP[i+1][j][1]+=DP[i][j][0]
      
    #SがN以下が確定しているものは、1~9をくっつけたものと、同じ桁だけどより低い数字が来たとき
    DP[i+1][j+1][1] += DP[i][j][1]*9+DP[i][j][0]*(max(0, int(S[i])-1))
print(sum(DP[-1][K]))

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
S = [0]+[int(c) for c in str(N)]
L = len(S)-1
dp0 = [[0]*(K+1) for i in range(L+1)]
dp1 = [[0]*(K+1) for i in range(L+1)]
dp0[0][0] = 0
dp1[0][0] = 1
for i in range(1,L+1):
  for j in range(K+1):
    if j==0:
      if S[i]>0:
        dp0[i][j] = dp0[i-1][j]+dp1[i-1][j]
      else:
        dp0[i][j] = dp0[i-1][j]
    else:
      if S[i]>0:
        dp0[i][j] = dp0[i-1][j]+dp0[i-1][j-1]*9+dp1[i-1][j]+dp1[i-1][j-1]*(S[i]-1)
        dp1[i][j] = dp1[i-1][j-1]
      else:
        dp0[i][j] = dp0[i-1][j]+dp0[i-1][j-1]*9
        dp1[i][j] = dp1[i-1][j]
print(dp1[-1][-1]+dp0[-1][-1])

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
S = [0]+[int(c) for c in str(N)]
L = len(S)-1
dp0 = [[0]*(K+1) for i in range(L+1)]
dp1 = [[0]*(K+1) for i in range(L+1)]
dp0[0][0] = 0
dp1[0][0] = 1
for i in range(1,L+1):
  for j in range(K+1):
    if j==0:
      if S[i]>0:
        dp0[i][j] = dp0[i-1][j]+dp1[i-1][j]
      else:
        dp0[i][j] = dp0[i-1][j]
    else:
      if S[i]>0:
        dp0[i][j] = dp0[i-1][j]+dp0[i-1][j-1]*9+dp1[i-1][j]+dp1[i-1][j-1]*(S[i]-1)
        dp1[i][j] = dp1[i-1][j-1]
      else:
        dp0[i][j] = dp0[i-1][j]+dp0[i-1][j-1]*9
        dp1[i][j] = dp1[i-1][j]
print(dp1[-1][-1]+dp0[-1][-1])

Submission status: Accepted

Solution code:
import math

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

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

def count(num_str,k):
    digits = len(num_str)
    if digits == 0:
        return 0
    else:
        if k == 0:
            # print(num_str,1)
            return 1
        if num_str[0] == '0':
            # print(num_str,count(num_str[1:],k-1))
            return count(num_str[1:],k)
        else:
            if digits == 1 and k == 1:
                # print(num_str,int(num_str))
                return int(num_str)
            elif digits == 1 and k > 1:
                # print(num_str,0)
                return 0
            if digits >= k+1:
                count_0 = combinations_count(digits-1,k)*(9**k)
            else:
                count_0 = 0
            count_1 = combinations_count(digits-1,k-1)*(9**(k-1))
            # print(num_str,count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1))
        return count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1)

print(count(str(n),k))

Submission status: Accepted

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

Nstr = str(N)

l = len(Nstr)

DP = [[[0]*2 for j in range(K+1)] for i in range(l+1)]

DP[0][0][1] = 1

for i in range(l):
    if int(Nstr[i])==0:
        for j in range(K+1):
            DP[i+1][j][0] += DP[i][j][0]
            DP[i+1][j][1] += DP[i][j][1]
            if j>0:
                DP[i+1][j][0] += 9*DP[i][j-1][0]
    else:
        for j in range(K+1):
            DP[i+1][j][0] += DP[i][j][0]+DP[i][j][1]
            if j>0:
                DP[i+1][j][0] += (int(Nstr[i])-1)*DP[i][j-1][1]+9*DP[i][j-1][0]
                DP[i+1][j][1] += DP[i][j-1][1]

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

Submission status: Accepted

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

Nstr = str(N)
Nlen = len(Nstr)

'''------dp設定-------
dp[i][j][k] 
dp[][][] 
i:桁数
j:非0の数を使った回数
k: 0:それまでの桁数は、Nと同じ
   1:それまでの桁数で、Nより小さいが確定
配るdpで更新
'''

#初期化
dp = [[[0 for i3 in range(2)] for i2 in range(K+1)] for i1 in range(Nlen+1)]
dp[0][0][0] = 1

#今の桁から次の桁に配るループ
for i in range(Nlen):
    for j in range(4):
        for k in range(2):
            nd = int(Nstr[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[Nlen][K][0]+dp[Nlen][K][1])

Submission status: Accepted

Solution code:
n=int(input())
m=len(str(n))
k=int(input())
N=[int(i) for i in str(n)]
dp0=[[0]*(k+1) for _ in range(m+1)]
dp1=[[0]*(k+1) for _ in range(m+1)]
dp1[0][0]=1
for i in range(m):
  for j in range(k+1):
    dp1[i+1][j]+=dp1[i][j]*(N[i]==0)
    dp0[i+1][j]+=dp0[i][j]+dp1[i][j]*(N[i]>0)
    if j<k:
      dp1[i+1][j+1]+=dp1[i][j]*(N[i]>0)
      dp0[i+1][j+1]+=dp0[i][j]*9+dp1[i][j]*max(0,N[i]-1)
print(dp1[m][k]+dp0[m][k])

Submission status: Accepted

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

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

dp[0][0][0]=1
keta=int(n[0])
dp[1]=[[0,1],[1,keta-1],[0,0],[0,0]]
  
for i in range(1,m):
  keta=int(n[i])
  dp[i+1][0][0]+=dp[i][0][0]*(keta==0)
  dp[i+1][0][1]+=(dp[i][0][0]*(keta>0)+dp[i][0][1])
  for j in range(3):
    dp[i+1][j+1][0]+=dp[i][j][0]*(keta!=0)+dp[i][j+1][0]*(keta==0)
    dp[i+1][j+1][1]+=(dp[i][j][0]*max(keta-1,0)+dp[i][j][1]*9
                      +dp[i][j+1][0]*(keta>0)+dp[i][j+1][1])
    
                    
print(dp[m][k][0]+dp[m][k][1])

Submission status: Accepted

Solution code:
#!python3

from math import factorial

iim = lambda: map(int, input().rstrip().split())

def cmb(a, b):
    c = a - b
    if c < b:
        b = c
    if b == 0: return 1

    ans = 1
    for i in range(b):
        ans *= a - i

    return ans // factorial(b)

def cnt(N, K):
    if K == 0:
        return 1

    n10 = 10 ** (K-1)
    if N < n10:
        return 0

    n10 *= 10
    n9 = 9 ** K

    ans = 0
    a = n10
    i = 0
    while a < N:
        a *= 10; i += 1
    a //= 10; i -= 1
    if i >= 0:
        ans = cmb(i+K, K) * n9
        #print(f"{i+K}C{K}", ans)

    n, b = divmod(N, a)
    if n > 1:
        ans += (n - 1) * cnt(a-1, K - 1)
    ans += cnt(b, K - 1)


    return ans

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

    print(cnt(N, K))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from functools import lru_cache
N = int(input())
K = int(input())
@lru_cache(None)
def F(N,K):
#  assert N>=0
  if N<10:
    if K==0:
      return 1
    if K==1:
      return N
    return 0
  p, q = divmod(N,10)
  ret = 0
  if K>0:
    ret += F(p,K-1) * q
    ret += F(p-1,K-1) * (9-q)
  ret += F(p,K)
  return ret
print(F(N,K))

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
A = 0
keta = len(str(N))
if K ==1:
    A = 9*(keta-1)
if K ==2:
    A = 9*9*(keta-1)*(keta-2)//2
if K ==3:
    A = 9*9*9*(keta-1)*(keta-2)*(keta-3)//6
nc = 1
#    print(N,K,keta,A)
while nc <= 3 and keta >=1:
        # abcd... -> 1000000 - a0000000
    T = N//(10**(keta-1))%10
#        print(T,nc)
    if T == 0:
        keta -=1
    else:
        if (nc == 1 and K==1) or (nc==2 and K==2) or (nc==3 and K==3):
            A = A + (T)
        if ((nc == 1 and K ==2) or (nc ==2 and K==3)):
            A = A + int((T-1)*9*(keta-1))
        if (nc==2 and K==2) or (nc==3 and K==3):
            A = A + 9*(keta-1)
        if (nc==1 and K ==3):
            A = A + int((T-1)*9*9*(keta-1)*(keta-2)/2)
        if (nc==2 and K==3):
            A = A + int(9*9*(keta-1)*(keta-2)/2)
        nc +=1
        keta -=1
#        print(A)
        
print(A)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# vim:fenc=utf-8 ff=unix


def solv(N, K):
    # print('solv', N, K)
    # K == 0 なら条件を満たしたものが一つある
    if K == 0:
        # print('   ret', 1)
        return 1
    # len(N) < K ならば不可能
    if len(N) < K:
        # print('   ret', 0)
        return 0

    # 場合の数
    count = 0

    #  3abcd のような 場合
    #  29999
    #  19999 のような数を加算する
    if N[0] > 1:
        count += (N[0]-1) * solv([9] * (len(N)-1), K-1)
    #  その数を消費する場合
    if N[0] > 0:
        count += solv(N[1:], K-1)
    # 消費しない場合
    if N[0] == 0:
        count += solv(N[1:], K)
    else:
        count += solv([9] * (len(N)-1), K)

    # print('   ret count=', count)
    return count


if __name__ == "__main__":

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

    print(ans)

Submission status: Accepted

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


DP = [[0]*(k+3), [0]*(k+3)]
DP[0][0] = 1

for num in n:
    num = int(num)

    for num_count in range(k+1, -1, -1):
        DP[1][num_count] += DP[1][num_count-1] * 9 + DP[0][num_count-1] * max(0, num-1)

        if num != 0:
            DP[0][num_count] = DP[0][num_count-1] * 1
            DP[1][num_count-1] += DP[0][num_count-1]
            DP[0][num_count-1] = 0

        else:
            continue

ans = DP[1][k] + DP[0][k]
print(ans)

Submission status: Accepted

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

n = len(s)

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)

Submission status: Accepted

Solution code:
from functools import lru_cache
N = int(input())
K = int(input())

@lru_cache(None)

def F(N,K):
  assert N>=0
  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:
def f(s,t,k):
 n=len(s)
 if k>n: return 0
 a=max(t,int(s[0]))
 z=0
 if a==0:z=f(s[1:],t,k)
 elif k==1:z=a+(n-1)*9
 else:
  if k-1<=n:z+=f(s[1:],9,k)
  z+=(a-1)*f(s[1:],9,k-1)
  z+=f(s[1:],t,k-1)
 return z
print(f(input(),0,int(input())))

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 functools import lru_cache
import bisect
import re
import queue


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 [input() 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 [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("Sample.txt")
    N = Scanner.string()
    K = Scanner.int()
    M = len(N)
    dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(M + 1)]
    dp[0][0][0] = 1
    for i in range(M):
        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:
                            nk = 1
                        if d > nd:
                            continue
                    dp[ni][nj][nk] += dp[i][j][k]
    ans = dp[M][K][0] + dp[M][K][1]
    print(ans)
    return


if __name__ == "__main__":
    main()