102355: [AtCoder]ABC235 F - Variety of Digits
Description
Score : $500$ points
Problem Statement
Given are $M$ digits $C_i$.
Find the sum, modulo $998244353$, of all integers between $1$ and $N$ (inclusive) that contain all of $C_1, \ldots, C_M$ when written in base $10$ without unnecessary leading zeros.
Constraints
- $1 \leq N < 10^{10^4}$
- $1 \leq M \leq 10$
- $0 \leq C_1 < \ldots < C_M \leq 9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $C_1$ $\ldots$ $C_M$
Output
Print the answer.
Sample Input 1
104 2 0 1
Sample Output 1
520
Between $1$ and $104$, there are six integers that contain both 0 and 1 when written in base $10$: $10,100,101,102,103,104$.
The sum of them is $520$.
Sample Input 2
999 4 1 2 3 4
Sample Output 2
0
Between $1$ and $999$, no integer contains all of 1, 2, 3, 4.
Sample Input 3
1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890 5 0 2 4 6 8
Sample Output 3
397365274
Be sure to find the sum modulo $998244353$.
Input
题意翻译
现在给你 $M$ 个数字 $c_1,c_2,\dots,c_M$。 求 $n$ 以内有多少个数满足，去掉前导零后，$M$ 个给定数字在剩下的数字中出现。 $n \le 10^{10^4}$，$M \le 10$。Output
问题描述
给出$M$个数字$C_i$。
找出在不带不必要的前导零的情况下，以十进制表示时包含$C_1, \ldots, C_M$的所有介于1和N（包括）之间的整数的和，对998244353取模。
限制条件
- $1 \leq N < 10^{10^4}$
- $1 \leq M \leq 10$
- $0 \leq C_1 < \ldots < C_M \leq 9$
- 输入中的所有值都是整数。
输入
输入将从标准输入以以下格式给出：
$N$ $M$ $C_1$ $\ldots$ $C_M$
输出
打印答案。
样例输入1
104 2 0 1
样例输出1
520
在1和104之间，当以十进制表示时，有六个整数同时包含0和1：10,100,101,102,103,104。
它们的和为520。
样例输入2
999 4 1 2 3 4
样例输出2
0
在1和999之间，没有整数同时包含1,2,3,4。
样例输入3
1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890 5 0 2 4 6 8
样例输出3
397365274
确保找到对998244353取模后的和。