AT_abc154_e [ABC154E] Almost Everywhere Zero

题目描述

请你求出在 $1$ 到 $N$ 之间（包含 $N$）的所有整数中，十进制表示下恰好有 $K$ 个非零数字的数的个数。

输入格式

输入从标准输入中以如下格式给出。

$N$ $K$

输出格式

输出满足条件的数的个数。

输入输出样例 #1

输入 #1

100
1

输出 #1

19

输入输出样例 #2

输入 #2

25
2

输出 #2

14

输入输出样例 #3

输入 #3

314159
2

输出 #3

937

输入输出样例 #4

输入 #4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

输出 #4

117879300

说明/提示

限制条件

• $1 \leq N < 10^{100}$
• $1 \leq K \leq 3$

样例解释 1

满足条件的数共有 $19$ 个。分别是 $1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100$。

样例解释 2

满足条件的数共有 $14$ 个。分别是 $11,12,13,14,15,16,17,18,19,21,22,23,24,25$。

由 ChatGPT 4.1 翻译