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: Runtime Error

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N = iip(False)
    K = iip(False)
    ret = solve(N, K)
    print(ret)

def solve(N, K):

    strn = str(N)

    A = []
    B = []

    for i in range(len(strn), 0, -1):
        if strn[len(strn)-i] != "0":
            A.append(int(strn[len(strn)-i]))
            B.append(i)


    if K == 1:
        return 9*(B[0]-1) + A[0]


    if K == 2:
        ret = 0
        ret += (B[0]-1) * (B[0]-2) // 2 * (9**2) #桁数がmaxじゃない場合
        ret += (A[0]-1) * 9 * (B[0]-1) #桁数がmaxで先頭桁がmax以外の場合
        ret += (B[1]-1) * 9 + A[1] #先頭桁がmaxの場合
        return ret

    ret = 0
    ret += (B[0] - 1) * (B[0] - 2) * (B[0] - 3) // 6 * 9**3 #桁数がmaxじゃない場合
    ret += (A[0] - 1) * (B[0] - 1) * (B[0] - 2) // 2 * 9**2 #桁数がmaxで先頭桁がmaxじゃない場合

    #以下、桁数はmaxで先頭桁はmaxとする
    ret += (B[1]-1) * (B[1]-2) // 2 * 9**2 #有効2桁目の桁数がmaxじゃない場合
    ret += (A[1] - 1) * (B[1]-1) * 9 #有効2桁目の桁数がmaxで数字がmaxじゃない場合
    ret += (B[2] - 1) * 9 + A[2] #有効2桁目,3桁目がmaxの場合
    return ret





#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
n = input()
k = int(input())
a = [int(n[i]) for i in range(min(k, len(n)))]
n = len(n)

if k > n:
    ans = 0
elif k == 1:
    # n 桁目に非負整数
    ans += a[0]
    # n 桁目以外に非負整数
    ans += (n - 1)*9
elif k == 2:
    # 上と同様
    ans += a[1] + (n - 2)*9
    # n 桁目の最大ではない非負整数と n-1 桁目以降に 1 つ非負整数
    ans += (a[0] - 1)*(n - 1)*9
    # n-1 桁目以降の中から 2 つ非負整数
    ans += (n - 1)*(n - 2)*9*9//2
else:
    # 上と同様
    ans += a[2] + (n - 3)*9 + (n - 2)*(n - 3)*9*9//2
    if a[1] != 0:
        ans += (a[1] - 1)*(n - 2)*9
    # n 桁目の最大でない非負整数と n-1 桁目以降に 2 つ非負整数
    ans += (a[0] - 1)*(n - 1)*(n - 2)*9*9//2
    # n-1 桁目以降から 3 つ非負整数
    ans += (n - 1)*(n - 2)*(n - 3)*9*9*9//6
print(ans)

Submission status: Runtime Error

Solution code:
n=input()
l=len(n)
k=int(input())
def f(n,k):
  l=len(n)
  if n[0]=="0":return f(n[1:],k)
  if l<k:return 0
  if k==1:
    ans=((l-1)*9)+int(n[0])
  if k==2:
    ans=((l-1)*(l-2)//2)*81+(int(n[0])-1)*((l-1)*9)
    ans+=f(n[1:],k-1)
  if k==3:
    ans=(int(n[0])-1)*((l-1)*(l-2)//2)*81+((l-1)*(l-2)*(l-3)//6)*9*9*9
    ans+=f(n[1:],k-1)
  return ans
print(f(n,k))

Submission status: Runtime Error

Solution code:
n=input()
if n[0]=="0"ans=1/0
l=len(n)
k=int(input())
if l<6:
  n=int(n)
  ans=0
  for i in range(1,n+1):
    if len(str(i))-str(i).count("0")==k:ans+=1
  print(ans)
  exit()
if k==1:
  ans=((l-1)*9)+int(n[0])
  print(ans)
if k==2:
  ans=((l-1)*(l-2)//2)*81
  ans+=(int(n[0])-1)*((l-1)*9)
  ans+=int(n[1])
  ans+=(l-2)*9
  print(ans)
if k==3:
  ans=int(n[2])+(l-3)*9
  ans+=(int(n[1])-1)*((l-2)*9)
  ans+=((l-2)*(l-3)//2)*81
  ans+=(int(n[0])-1)*((l-1)*(l-2)//2)*81
  ans+=((l-1)*(l-2)*(l-3)//6)*9*9*9
  print(ans)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
import time

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

N_len = len(N)

ans = 0
if K == 1:
    time.sleep(0.3)
    ans = int(N[0]) + 9 * (N_len-1)
elif K == 2:
    time.sleep(0.6)
    if N_len >= 2:
        ans = (int(N[0])-1) * 9 *(N_len-1)
        ans += int(N[1]) + 9 * (N_len-2)
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
    time.sleep(0.9)
    if N_len >= 3:
        # N[0],N[1]
        ans = int(N[2]) + 9 * (N_len-3)
        # N[0], 1~N[1]-1
        ans += max(int(N[1])-1,0) * 9 * (N_len-2)
        # N[0], N[1] = 0
        ans += 9**2 * comb(N_len-2,2,exact=True)
        # 1~N[0]-1
        ans += (int(N[0])-1) * 9**2 * comb(N_len-1,2,exact=True)     
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)

Submission status: Runtime Error

Solution code:
from scipy.misc import comb
import time

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

N_len = len(N)

ans = 0
if K == 1:
  	time.sleep(0.5)
    ans = int(N[0]) + 9 * (N_len-1)
elif K == 2:
  	time.sleep(1)
    if N_len >= 2:
        ans = (int(N[0])-1) * 9 *(N_len-1)
        ans += int(N[1]) + 9 * (N_len-2)
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
  	time.sleep(1.5)
    if N_len >= 3:
        # N[0],N[1]
        ans = int(N[2]) + 9 * (N_len-3)
        # N[0], 1~N[1]-1
        ans += max(int(N[1])-1,0) * 9 * (N_len-2)
        # N[0], N[1] = 0
        ans += 9**2 * comb(N_len-2,2,exact=True)
        # 1~N[0]-1
        ans += (int(N[0])-1) * 9**2 * comb(N_len-1,2,exact=True)     
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
# sys.setrecursionlimit(1000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
mod = 998244353

N = [int(x) for x in input()]
K = int(input())
dp = [[[0]*2 for j in range(K+1)] for i in range(len(N)+1)]
dp[0][0][1] = 1
for i in range(len(N)):
    dp[i+1][0][0] = 1
    if N[i] == 0:
        for k in range(1, K+1):
            dp[i+1][k][0] = dp[i][k][0]+dp[i][k-1][0]*9
            dp[i+1][k][1] = dp[i][k][1]
    else:
        for k in range(1, K+1):
            dp[i+1][k][0] = dp[i][k][0]+dp[i][k-1][0]*9+dp[i][k-1][1]*(N[i]-1)+dp[i][k][1]
        for k in range(K-1, -1, -1):
            if dp[i][k][1]:
                print(i, k, N[i])
                dp[i+1][k+1][1] = dp[i][k][1]
                break
print(dp)
print(dp[len(N)][K][0]+dp[len(N)][K][1])

Submission status: Runtime Error

Solution code:
from itertools import combinations, product
from math import factorial

def nCr(n, r):
  return int(factorial(n) / factorial(n - r) / factorial(r))

n = int(input())
k = int(input())
size = len(str(n))
count = 0 if k > size - 1 else (nCr(size - 1, k) * (9 ** k))
if k == 1:
  count += sum(i * (10 ** (size - 1)) <= n for i in range(1, 10))
else:
  first = int(str(n)[0])
  count += (first - 1) * nCr(size - 1, (k - 1)) * (9 ** (k - 1))
  for digits in combinations(range(size - 1), k - 1):
    count += sum(
      sum(num * (10 ** digit) for num, digit in zip(nums, digits)) <= n % (10 ** (size - 1))
      for nums in product(range(1, 10), repeat = k - 1)
    )
print(count)

Submission status: Runtime Error

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

def K1(N):
  le = len(N)
  if le == 1:
    return int(N)
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    return 0
  else:
    j=1
    if int(N[j]) == 0:
      while int(N[j]) == 0:
        j+=1
        if j == le-1:
          break
        
    n = N[j:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    return 0
  else:
    j=1
    if int(N[j]) == 0:
      while int(N[j]) == 0:
        j+=1
        if j == le-1:
          break
        
    n2 = N[j:le]
    
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))

Submission status: Runtime Error

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

def K1(N):
  le = len(N)
  if le == 1:
    return int(N)
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    return 0
  else:
    j=1
    if int(N[j]) == 0:
      while int(N[j]) == 0:
        j+=1
        
    n = N[j:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    return 0
  else:
    j=1
    if int(N[j]) == 0:
      while int(N[j]) == 0:
        j+=1
        
    n2 = N[j:le]
    
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))

Submission status: Runtime Error

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

def K1(N):
  le = len(N)
  if le == 1:
    return int(N)
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    return 0
  else:
    j=1
    for i in range(le-1):
      if int(N[i+1]) == 0:
        j+=1
      
    n = N[j:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    return 0
  else:
    j=1
    for i in range(le-1):
      if int(N[i+1]) == 0:
        j+=1
    n2 = N[j:le]
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))

Submission status: Runtime Error

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

def K1(N):
  le = len(N)
  if le == 1:
    print(int(N))
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    print(0)
  else:
    n = N[1:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    print(0)
  else:
    n1 = N[2:le]
    n2 = N[1:le]
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))

Submission status: Runtime Error

Solution code:
def comb(x,y):
    if y==1:
        return x
    elif y==2:
        return max(x*(x-1)//2, 0)
    elif y==3:
        return max(x*(x-1)*(x-2)//6, 0)


n = int(input())
k = int(input())
digit = len(str(n))
ans1 = comb(digit-1, k) * (9**k)
lst = [int(i) for i in list(str(n))]
if k==1:
    ans2 = lst[0]
elif k==2:
    ans2 = 0
    ans2 += (lst[0]-1) * (digit-1) * 9
    ans2 += lst[1] + (digit-2)*9
elif k==3:
    ans2 = 0
    ans2 += (lst[0]-1) * comb(digit-1, 2) * (9*2)
    ans2 += lst[1]*(digit-2)*9 + comb(digit-2, 2)*(9**2)
print(ans1+ans2)

Submission status: Runtime Error

Solution code:
def comb(x,y):
    if y==1:
        return x
    elif y==2:
        return max(x*(x-1)//2, 0)
    elif y==3:
        return max(x*(x-1)*(x-2)//6, 0)


n = int(input())
k = int(input())
digit = len(str(n))

ans1 = comb(digit-1, k) * (9**k)

lst = [int(i) for i in list(str(n))]
if k==1:
    ans2 = lst[0]
elif k==2:
    ans2 = 0
    ans2 += (lst[0]-1) * (digit-1) * 9
    ans2 += lst[1] + (digit-2)*9
elif k==3:
    ans2 = 0
    ans2 += (lst[0]-1) * comb(digit-1, 2) * (9**2)
    ans2 += lst[1]*(digit-2)*9 + comb(digit-2, 2)*(9**2)
    
print(ans1+ans2)

Submission status: Runtime Error

Solution code:
n=input()
k=input()
sum=0
for i in range(1,k+1):
    a=list(str(i))
    if list.count(0)=k:
        sum+=1
print(sum)

Submission status: Runtime Error

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

a = 1
b = [0] * (K + 1)
b[0] = 1
b[1] = int(N[0]) - 1

for c in N[1:]:
    t = int(c)
    for i in range(K - 1, -1, -1):
        b[i + 1] += b[i] * 9
    if t != 0:
        b[a + 1] += t - 1
        b[a] += 1
        a += 1

if a == K:
    print(b[K] + 1)
else:
    print(b[K])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE
string N;
Int K;

int used[101][2][2][101];
int mem[101][2][2][101];

Int dfs(Int idx, Int allZero, Int same, Int cnt, string s){
  if(idx >= Int(N.size())) return cnt == K;
  if(cnt > K) return 0;
  if(used[idx][allZero][same][cnt]++) return mem[idx][allZero][same][cnt];

  int res = 0;
  for(Int i=0;i<10;i++){
    Int nidx = idx + 1;
    Int nallZero = allZero && (i == 0);
    Int nsame = same && (N[idx] == i + '0');
    Int ncnt = cnt + (i != 0);
    if(same && N[idx] < i + '0') continue;
    res += dfs(nidx, nallZero, nsame, ncnt, "");
  }
  return mem[idx][allZero][same][cnt] = res;

}

signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin>>N>>K;

  Int ans = dfs(0, 1, 1, 0, "");
  cout<<ans<<endl;

  return 0;
}

Submission status: Runtime Error

Solution code:
import itertools
import sys

def cmb(n, r):
	if n - r < r: r = n - r
	if r == 0: return 1
	if r == 1: return n
	if r < 0: return 0

	numerator = [n - r + k + 1 for k in range(r)]
	denominator = [k + 1 for k in range(r)]

	for p in range(2,r+1):
		pivot = denominator[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p-1,r,p):
				numerator[k - offset] /= pivot
				denominator[k] /= pivot

	result = 1
	for k in range(r):
		if numerator[k] > 1:
			result *= int(numerator[k])

	return result

n = input()
k = int(input())
l = len(n)

if l < k:
	print(0)
	sys.exit()
elif l == 1 and k == 1:
	print(n)
	sys.exit()

#dp[i][j] = i桁目までで、0でない数字がちょうどj個あるようなものの個数
dp = [[0 for _ in range(4)]for _ in range(l+1)]
dp[1][0] = 1

for i in range(1,l+1):
	for j in range(4):
		if i >= j:
			dp[i][j] = cmb(i,j) * (9**j)

ans = dp[l-1][k]
ans += (int(n[0]) - 1) * dp[l-1][k-1]

num = l
for i in range(1,l):
	if n[i] != '0':
		num = i
		break
if num == l:
	if n.count('0') == l-k:
		print(ans+1)
	else:
		print(ans)
	sys.exit()

tmp1 = (int(n[num])-1) * cmb(9,k-2)
tmp2 = 9**(k-1)

for v in itertools.combinations(range(num,l), k-1):
	if num in v:
		if len(v) == 2:
			t = int(n[v[i]])
		else:
			t = 1
		ans += tmp1 + t
	else:
		ans += tmp2

print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import sys

def cmb(n, r):
	if n - r < r: r = n - r
	if r == 0: return 1
	if r == 1: return n

	numerator = [n - r + k + 1 for k in range(r)]
	denominator = [k + 1 for k in range(r)]

	for p in range(2,r+1):
		pivot = denominator[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p-1,r,p):
				numerator[k - offset] /= pivot
				denominator[k] /= pivot

	result = 1
	for k in range(r):
		if numerator[k] > 1:
			result *= int(numerator[k])

	return result

n = input()
k = int(input())
l = len(n)

if l < k:
	print(0)
	sys.exit()
elif l == 1 and k == 1:
	print(n)
	sys.exit()

#dp[i][j] = i桁目までで、0でない数字がちょうどj個あるようなものの個数
dp = [[0 for _ in range(4)]for _ in range(l+1)]
dp[1][0] = 1

for i in range(1,l+1):
	for j in range(4):
		if i >= j:
			dp[i][j] = cmb(i,j) * (9**j)

ans = dp[l-1][k]
ans += (int(n[0]) - 1) * dp[l-1][k-1]

tmp1 = (int(n[1])-1) * cmb(9,k-2)
tmp2 = 9**(k-1)
c = 0
for v in itertools.combinations(range(1,l), k-1):
	#print(v)
	if 1 in v:
		t = 1
		for i in range(len(v)):
			t *= int(n[v[i]])
		t = t // int(n[1])
		ans += tmp1 + t
	else:
		ans += tmp2

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

def cmb(n, r):
	if n - r < r: r = n - r
	if r == 0: return 1
	if r == 1: return n

	numerator = [n - r + k + 1 for k in range(r)]
	denominator = [k + 1 for k in range(r)]

	for p in range(2,r+1):
		pivot = denominator[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p-1,r,p):
				numerator[k - offset] /= pivot
				denominator[k] /= pivot

	result = 1
	for k in range(r):
		if numerator[k] > 1:
			result *= int(numerator[k])

	return result

n = input()
k = int(input())
l = len(n)

#dp[i][j] = i桁目までで、0でない数字がちょうどj個あるようなものの個数
dp = [[0 for _ in range(4)]for _ in range(l+1)]
dp[1][0] = 1

for i in range(1,l+1):
	for j in range(4):
		if i >= j:
			dp[i][j] = cmb(i,j) * (9**j)

ans = dp[l-1][k]
ans += (int(n[0]) - 1) * dp[l-1][k-1]

tmp1 = (int(n[1])-1) * cmb(9,k-2)
tmp2 = 9**(k-1)
c = 0
for v in itertools.combinations(range(1,l), k-1):
	#print(v)
	if 1 in v:
		t = 1
		for i in range(len(v)):
			t *= int(n[v[i]])
		t = t // int(n[1])
		ans += tmp1 + t
	else:
		ans += tmp2

print(ans)

Submission status: Runtime Error

Solution code:
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
#include<functional>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<tuple>
#include<iostream>
#include<string>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define REP(i,x) for (int i=0;i<x;i++)
#define REPP(i,x,y) for (int i=x;i<=y;i++)
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define MX3(x,y,z) max({x,y,z})
#define MX4(x,y,z,p) max({x,y,z,p})
#define MX5(x,y,z,p,q) max({x,y,z,p,q})
#define MN3(x,y,z) min({x,y,z})
#define MN4(x,y,z,p) min({x,y,z,p})
#define MN5(x,y,z,p,q) min({x,y,z,p,q})
#define amax(x,y) x=max(x,y)
#define amin(x,y) x=min(x,y)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vb> vvb;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef tuple<int,int,int> ti;
typedef tuple<ll,ll,ll> tl;
// #####################################################################
char arr[200];
char tmp[200];

void solve() {

    scanf("%s", arr);
    int k;
    SI(k);
    int n = strlen(arr);
    int ans = 0;
    
    if(k == 1) {
        ans += 9 * (n - 1);
        ans += arr[0] - '0';
    }
    tmp[n] = 0;
    REP(i, n) tmp[i] = '0';

    if(k == 2) {

        if(n - 1 >= 2) {
            ans += (n-1) * (n-2) / 2 * 9 * 9;
        }
        if(n >= 2) {
            for(int i = 1 ; i <= 9 ; i++) {
                tmp[0] = i + '0';
                for(int z = 1 ; z < n ; z++) {
                    for(int j = 1 ; j <= 9 ; j++) {
                        tmp[z] = j + '0';
                        if(strcmp(arr, tmp) >= 0) {
                            ans++;
                        }
                    }
                    tmp[z] = '0';
                }
                tmp[0] = '0';
            }
        }
    }

    if(k == 3) {
        
        if(n - 1 >= 3) {
            ans += (n-1) * (n-2) * (n-3) / 6 * 9 * 9 * 9;

        }
        if(n >= 3) {
            for(int i = 1 ; i <= 9 ; i++) {
                tmp[0] = i + '0';
                for(int z = 1 ; z < n ; z++) {
                    for(int y = z+1 ; y < n ; y++) {
                        for(int j = 1 ; j <= 9 ; j++) {
                            tmp[z] = j + '0';
                            for(int kk = 1 ; kk <= 9 ; kk++) {
                                tmp[y] = kk + '0';
                                if(strcmp(arr, tmp) >= 0) {
                                    ans++;
                                }
                                tmp[y] = '0';
                            }
                            tmp[z] = '0';
                        }
                    }
                }
                tmp[0] = '0';
            }
        }
    }

    printf("%d\n", ans);
}

void init() {
    


}

int main () {
    init();
    solve();
    return 0;
}

Submission status: Runtime Error

Solution code:
def main():
    s = [int(char) for char in input()]
    l = len(s)
    k = int(input())

    tmp = 0
    nonzero = []
    for number in s:
        if number > 0:
            tmp += 1
        nonzero.append(tmp)
    nonzero.append(0)  # let nonzero[-1] be 0

    def binomial(n, k):
        if n < k or n < 0 or k < 0:
            raise ValueError
        if k == 0:
            return 1
        if k == 1:
            return n
        if k == 2:
            return n * (n-1) // 2
        if k == 3:
            return n * (n-1) * (n-2) // 6
        raise ValueError

    def dp(i, _cache={-1: 0}):
        if i in _cache:
            return _cache[i]
        if nonzero[i-1] > k or s[i] == 0:
            result = dp(i-1)
            _cache[i] = result
            return result
        if nonzero[i-1] == k:
            result = dp(i-1) + 1
            _cache[i] = result
            return result
        result = (
            dp(i-1) +
            (s[i] - 1) * binomial(l - 1 - i, k - nonzero[i-1] - 1) *
            9 ** (k - nonzero[i-1] - 1) +
            binomial(l - 1 - i, k - nonzero[i-1]) *
            9 ** (k - nonzero[i-1])
        )
        _cache[i] = result
        return result
    
    print(dp(l-1) + (nonzero[l-1] == k))


main()

Submission status: Runtime Error

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

l = len(S)

MOD = 1000000007

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

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

for i in range(l):
    cur = int(S[i])

    for j in range(i + 1):
        for k in range(10):
            if k == 0:
                dp[i + 1][True][j] += dp[i][True][j]
            else:
                dp[i + 1][True][j + 1] += dp[i][True][j]
                
        for k in range(cur):
            if k == 0:
                dp[i + 1][True][j] += dp[i][False][j]
            else:
                dp[i + 1][True][j + 1] += dp[i][False][j]

        if cur == 0:
            dp[i + 1][False][j] += dp[i][False][j]
        else:
            dp[i + 1][False][j + 1] += dp[i][False][j]


print(dp[l][True][K] + dp[l][False][K])

Submission status: Runtime Error

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

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

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

for i in range(len(n)):
    if n[i] == "0":
        for j in range(k):
            dp[i + 1][j + 1][0] = dp[i][j][0]
            dp[i + 1][j + 1][1] = dp[i][j][1]
        for j in range(k+1):
            dp[i + 1][j][0] += dp[i][j][0] * 9
    else:
        for j in range(k):
            dp[i + 1][j + 1][0] = dp[i][j][0] + dp[i][j][1]
        for j in range(k+1):
            dp[i + 1][j][0] += dp[i][j][0] * 9+dp[i][j][1] * (int(n[i])-1)
            dp[i + 1][j][1] += dp[i][j][1]
print(sum(dp[-1][-1]))

Submission status: Runtime Error

Solution code:
from scipy.special import comb
def solve(i,k,smaller):
    print("i="+str(i))
    if i == len(S):
        if k == 0:
            #0以外の個数がkと等しいので答えとしてカウントできる
            return 1
        else:
            #0以外の個数がkと等しくないので答えとしてカウント不可
            return 0 
    
    if k ==0:
        #kの個数を使い切りこれ以上下の桁は0で埋まり1通りの為
        return 1
    
    if smaller :
        return comb(len(S)-i,k)*pow(9,k)
    else:
        if S[i] =="0":
            return solve(i+1,k,False)
        else:
            zero = solve(i+1,k,True)
            aida = solve(i+1,k-1,True)*(int(S[i])-1)
            ici  = solve(i+1,k-1,False)
            return zero+aida+ici
            
N = int(input())
S = str(N)
K = int(input())

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

Submission status: Runtime Error

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

#桁DP
string = str(N)
digits = len(string)

#dp[i][j][k]=と同じ桁数の整数で上からi桁目までで0でない数字がj個あるものの個数
#k=0: i桁目まで見てN未満が確定, k=1: 未確定
dp = [[[0]*2 for _ in range(K+1)] for __ in range(digits+1)]
#初期状態
dp1[0][0][1] = 1

for i in range(digits):
    d = int(string[i])
    ni = i+1
    for j in range(K+1):
        for k in range(2):
            for nd in range(10):
                nk = 1 if k == 1 and nd == d else 0
                if k == 1 and nd > d: break

                nj = j + (1 if nd != 0 else 0)
                if nj > K: continue

                dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Runtime Error

Solution code:
import numpy as np

N=int(input())
n=[int(i) for i in str(N)]
K=int(input())
L=len(n)
dp=np.zeros((L+1,2,K+1),dtype=int)
dp[0,0,0]=1

for i in range(L):
  for smaller in [0,1]:
    for j in range(0,K):
      m=10 if smaller else n[i]+1
      for x in range(m):
        if ( (j+(x!=0)) <= K )
          #i桁目がxだったときにdp[i][smaller][j]をどこに足しますか？
          dp[i+1][smaller or x<n[i]][j+(x!=0)]+=dp[i][smaller][j]
        
print(dp[L,:,K].sum())

Submission status: Runtime Error

Solution code:
import functools

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

@functools.lru_cache(maxsize=2048)
def nCk(n, k):
    if k == 0:
        return 0
    elif k == 1:
        return n
    elif k == 2:
        return (n * (n-1)) // 2
    return (n * (n-1) * (n-2)) // 6

def slowsolve(N, K):
    ans = 0
    meta = {}
    for i in range(1, int(N) + 1):
        if len(str(i)) - str(i).count("0") == K:
            meta.setdefault(len(str(i)), 0)
            meta[len(str(i))] += 1
            ans += 1
    return ans, meta

def clean(N):
    clean_N = []
    for n in N:
        if n == "0" and not clean_N:
            pass
        else:
            clean_N.append(n)
    return "".join(clean_N)

@functools.lru_cache(maxsize=2048)
def solve(N, K):
    N = clean(N)

    if len(N) <= 3:
        return slowsolve(N, K)[0]
    elif K == 0:
        return 0
    else:
        m = int(N[0])

        # 一番上を0にする
        ans = solve("9" * len(N[1:]), K)

        if K == 3:
            # 一番上を1 ~ m - 1にする
            # => 下の部分から2か所選び、それぞれ1 ~ 9
            ans += (m - 1) * nCk(len(N[1:]), 2) * 9 * 9
            # 一番上をmにする
            ans += solve(N[1:], K - 1)
        elif K == 2:
            # 一番上を1 ~ m - 1にする
            # => 下の部分から1か所選び、1 ~ 9
            ans += (m - 1) * len(N[1:]) * 9
            # 一番上をmにする
            ans += solve(N[1:], K - 1)
        elif K == 1:
            # 一番上をmにする
            ans += m
        return ans

# for n in range(9999, 100000):
#     for k in range(1, 4):
#         ans = solve(str(n), k)
#         assert1, meta = slowsolve(str(n), k)
#         if ans != assert1:
#             print(ans, assert1, n, k)
#             print(meta)
#             assert(ans == assert1)
#
# # print(slowsolve(N, K))
print(solve(N, K))

Submission status: Runtime Error

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

x = [1]*(n_len)
for i in range(n_len-1):
    x[i+1] = x[i]*(i+1)

def calc(i,j):
    return x[i]/x[j]/x[i-j]*9**(j)
    
count = 0
non_zero = 0
for ind,i in enumerate(str(n)):
    if i != '0':
        non_zero += 1
        if n_len-ind-1 > k-non_zero:
            count += calc(n_len-ind-1,k-non_zero+1)
        if non_zero < k:
            count += calc(n_len-ind-1,k-non_zero)*(int(i)-1)
        elif non_zero == k:
            count += int(i)
            break
    
print(int(count))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

n=input()
x=len(n)
k=int(input())
l=[int(i) for i in n]
dp1=[[0]*(k+2) for i in range(x+1)]
dp2=[[0]*(k+2) for i in range(x+1)]
dp2[0][0]=1
dp2[1][0]=1
dp2[1][1]=l[0]-1
for i in range(1,k+1):
    dp1[i][i]=1
for i in range(k,x+1):
    dp1[i][k]=1
for i in range(2,x+1):
    for j in range(k+1):
        if j==0:
            dp2[i][j]=1
        elif j<=i:
            dp2[i][j]+=max(0,l[i-1]-1)
            dp2[i][j]+=((dp2[i-1][j])+(dp2[i-1][j-1]*9))
            #print(i,j,dp2[i-1][j],dp2[i-1][j-1]*9)
print(dp1[x][k]+dp2[x][k])

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
n, k = map(int, read().split())


def count(digit, k):
    elif k == 0:
        return 1
    elif k == 1:
        return digit
    elif k == 2:
        return digit * (digit - 1) // 2
    else:
        return digit * (digit - 1) * (digit - 2) // 6


def solve(n, k):
    if k == 0:
        return 1
    digit = len(str(n))
    res = 0
    if digit > k:
        res += count(digit - 1, k) * (9 ** k)
    pow10 = 10 ** (digit - 1)
    d, mod = n // pow10, n % pow10
    res += count(digit - 1, k - 1) * (9 ** (k - 1)) * (d - 1)
    res += solve(mod, k - 1)
    return res


print(solve(n, k))

Submission status: Runtime Error

Solution code:
n=input()
k=int(input())
dp=[[[0]*(k+2) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0]=1
for i,c in enumerate(n):
	for f in range(2):
		for j in range(k+1):
			for l in range(10 if f else int(c)+1):
				dp[i+1][f or l<c][j+(l>0)]+=dp[i][f][j]
print(dp[-1][0][k]+dp[-1][1][k])