#314. [SNOI2022] 数位 - 洛谷

[SNOI2022] 数位 - 洛谷

当前没有测试数据。

题目描述

小 S 是一个喜欢数数的女孩子。

有一天,她在睡前躺在床上数数,当她数到 977431977431 的时候,她终于困了,并且决定睡觉。但此时她突然发现这个数字的各位数码是单调不增的!她觉得这相当有趣,于是她又睡不着了。

她想知道有多少个数在 L,RL, R 之间,并且它的各位数码是单调不增的。但这个问题太无聊了。

她又想知道有多少数对 (a,b)(a, b)L,RL, R 之间,并且 (a+b)(a + b) 的各位数码是单调不增的。但这个问题也太无聊了。

终于,她想到了一个有趣一些的问题:

给定整数 L,R,kL, R, k,求有多少个 kk 维向量 (a1,a2,...,ak)(a_1, a_2, ..., a_k) 满足 (a1+a2+...+ak)(a_1 + a_2 + ... + a_k) 的数码是单调不增的,并且 i[1,k],LaiR\forall i \in [1, k], L \leq a_i \leq R

由于答案可能很大,请你输出它对 998244353998244353 取模的结果。

输入格式

输入的第一行是一个正整数 LL,含义见【题目描述】

输入的第二行是一个正整数 RR,含义见【题目描述】。

输入的第三行是一个正整数 kk,含义见【题目描述】。

输出格式

输出一行一个整数表示合法的向量数,答案 998244353998244353 取模。

1
100
2
3728
19260817
1000000000
3
28745082
114514233
1919810233
10
135934411
样例 4 见附件 digit4.in
样例 4 见附件 digit4.ans
样例 5 见附件 digit5.in
样例 5 见附件 digit5.ans

提示

【数据规模与约定】

对于全部数据,1LR<1010001 \leq L \leq R < 10^{1000}1k501 \leq k \leq 50

具体的数据规模与约定见下表。

测试点编号 R<R< kk
11 10610^6 11
22 1010
33 2020
44 3030
55 5050
66 101710^{17} 1010
77
88 2020
99 3030
1010 5050
1111 105010^{50} 22
1212 1010
1313 1010010^{100} 22
1414 33
1515 1010
1616 1020010^{200} 33
1717 1010
1818 1030010^{300}
1919
2020 2020
2121 1050010^{500} 1010
2222 2020
2323 10100010^{1000} 3030
2424 5050
2525