AT_abc154_e [ABC154E] Almost Everywhere Zero

题目描述

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

输入格式

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

$N$ $K$

输出格式

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

样例 1

输入

100
1

输出

19

样例 2

输入

25
2

输出

14

样例 3

输入

314159
2

输出

937

样例 4

输入

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

输出

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 翻译