#2434. 数位
数位
数位
题目描述
2022 年陕西省NOI 省队选拔赛试题 数位(digit) 数位(digit) 【题目描述】 小S 是一个喜欢数数的女孩子。 有一天,她在睡前躺在床上数数,当她数到977431 的时候,她终于困了,并且决定睡觉。 但此时她突然发现这个数字的各位数码是单调不增的!她觉得这相当有趣,于是她又睡不着了。 她想知道有多少个数在L, R 之间,并且它的各位数码是单调不增的。但这个问题太无聊 了。 她又想知道有多少数对(a, b) 在L, R 之间,并且(a + b) 的各位数码是单调不增的。但这 个问题也太无聊了。 终于,她想到了一个有趣一些的问题: 给定整数L, R, k,求有多少个k 维向量(a1, a2, ..., ak) 满足(a1 + a2 + ... + ak) 的数码是 单调不增的,并且∀i ∈[1, k], L ≤ai ≤R。 她不会了。 由于答案可能很大,你只需要帮她求出答案对998244353 取模的结果。 【输入格式】 从文件digit.in 读入数据。 输入包含三行,第一行包含一个正整数L,第二行包含一个正整数R,第三行包含一个正 整数k,具体意义见【题目描述】。 【输出格式】 输出到文件digit.out 中。 输出一行一个非负整数,表示满足上述要求的k 维向量(a1, a2, ..., ak) 的个数对998244353 取模的值。 【样例输入1】 见选手目录下的digit/digit1.in。 1 100 2 【样例输出1】 见选手目录下的digit/digit1.ans。 3728 第11 页,共13 页
2022 年陕西省NOI 省队选拔赛试题 数位(digit) 【样例输入2】 见选手目录下的digit/digit2.in。 19260817 1000000000 3 【样例输出2】 见选手目录下的digit/digit2.ans。 28745082 【样例输入3】 见选手目录下的digit/digit3.in。 114514233 1919810233 10 【样例输出3】 见选手目录下的digit/digit3.ans。 135934411 【样例4】 见选手目录下的digit/digit4.in 和digit/digit4.ans。 【样例5】 见选手目录下的digit/digit5.in 和digit/digit5.ans。 【数据规模与约定】 对于全部数据,1 ≤L ≤R < 101000,1 ≤k ≤50。 具体的数据规模与约定见下表。 第12 页,共13 页
2022 年陕西省NOI 省队选拔赛试题 数位(digit) 测试点编号 R k 1 < 106 1 2 10 3 20 4 30 5 50 6 < 1017 10 7 8 20 9 30 10 50 11 < 1050 2 12 10 13 < 10100 2 14 3 15 10 16 < 10200 3 17 10 18 < 10300 19 20 20 21 < 10500 10 22 20 23 < 101000 30 24 50 25 第13 页,共13 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1
100
2
3728
样例 2
19260817
1000000000
3
28745082