AtCoder Beginner Contest 194
翻译中…
Problem Statement
翻译中…
In this problem, hexadecimal notations use 0, ..., 9, A, ..., F, representing the values zero through fifteen, respectively.
Unless otherwise specified, all notations of numbers are decimal notations.
翻译中…
How many integers between $1$ and $N$ (inclusive) have exactly $K$ distinct digits in the hexadecimal notation without leading zeros?
Print this count modulo $(10^9 + 7)$.
翻译中…
Constraints
翻译中…
$1 \le N \lt {16}^{2 \times 10^5}$$N$is given in hexadecimal notation without leading0s.$1 \le K \le 16$- All values in input are integers.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N K翻译中…
Here, $N$ is in hexadecimal notation.
翻译中…
Output
翻译中…
Print the count modulo $10^9 + 7$.
翻译中…
样例
Input #1
10 1
Output #1
15
The hexadecimal number $N$ is $16$ in decimal.
In hexadecimal, the integers between $1$ and $16$ are written as follows:
- $1$ through $15$: are $1$-digit numbers in hexadecimal, containing one distinct digit.
- $16$: is $10$ in hexadecimal, containing two distinct digits.
Thus, there are $15$ numbers that contain one distinct digit in hexadecimal.
Input #2
FF 2
Output #2
225
All of the $255$ numbers except the following $30$ numbers contain two distinct digits in hexadecimal: $1, 2, 3, \dots, \mathrm{E}, \mathrm{F}, 11, 22, 33, \dots, \mathrm{EE}, \mathrm{FF}$ in hexadecimal.
Input #3
100 2
Output #3
226
Input #4
1A8FD02 4
Output #4
3784674
Input #5
DEADBEEFDEADBEEEEEEEEF 16
Output #5
153954073
Print the count modulo $(10^9 + 7)$.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。