A6600 | 「SNOI2022」数位
时间限制6s
内存限制1024MB
通过 / 提交0/0
题目描述
小 S 是一个喜欢数数的女孩子。
有一天，她在睡前躺在床上数数，当她数到 $977431$ 的时候，她终于困了，并且决定睡觉。但此时她突然发现这个数字的各位数码是单调不增的！她觉得这相当有趣，于是她又睡不着了。
她想知道有多少个数在 $L, R$ 之间，并且它的各位数码是单调不增的。但这个问题太无聊了。
她又想知道有多少数对 $(a, b)$ 在 $L, R$ 之间，并且 $(a + b)$ 的各位数码是单调不增的。但这个问题也太无聊了。
终于，她想到了一个有趣一些的问题：
给定整数 $L, R, k$，求有多少个 $k$ 维向量 $(a_1, a_2, ..., a_k)$ 满足 $(a_1 + a_2 + ... + a_k)$ 的数码是单调不增的，并且 $\forall i \in [1, k], L \leq a_i \leq R$ 。
她不会了。
由于答案可能很大，请你输出它对 $998244353$ 取模的结果。
有一天，她在睡前躺在床上数数，当她数到 $977431$ 的时候，她终于困了，并且决定睡觉。但此时她突然发现这个数字的各位数码是单调不增的！她觉得这相当有趣，于是她又睡不着了。
她想知道有多少个数在 $L, R$ 之间，并且它的各位数码是单调不增的。但这个问题太无聊了。
她又想知道有多少数对 $(a, b)$ 在 $L, R$ 之间，并且 $(a + b)$ 的各位数码是单调不增的。但这个问题也太无聊了。
终于，她想到了一个有趣一些的问题：
给定整数 $L, R, k$，求有多少个 $k$ 维向量 $(a_1, a_2, ..., a_k)$ 满足 $(a_1 + a_2 + ... + a_k)$ 的数码是单调不增的，并且 $\forall i \in [1, k], L \leq a_i \leq R$ 。
她不会了。
由于答案可能很大，请你输出它对 $998244353$ 取模的结果。
输入格式
输入包含三行，第一行包含一个正整数 $L$，第二行包含一个正整数 $R$，第三行包含一个正整数 $k$，具体意义见「题目描述」。
输出格式
输出一行一个非负整数，表示满足上述要求的 $k$ 维向量 $(a_1, a_2, \ldots , a_k)$ 的个数对 $998244353$ 取模的值。
输入输出样例
输入 #1
1 100 2
输出 #1
3728
输入 #2
19260817 1000000000 3
输出 #2
28745082
输入 #3
114514233 1919810233 10
输出 #3
135934411
对于全部数据，$1\le L\le R< 10^{1000},1\le k\le 50$。
具体的数据规模与约定见下表。
| 测试点编号 | $R$ | $k$ |
| :--------: | :-----------: | :--: |
| $1$ | $< 10^6$ | $1$ |
| $2$ | $< 10^6$ | $10$ |
| $3$ | $< 10^6$ | $20$ |
| $4$ | $< 10^6$ | $30$ |
| $5$ | $< 10^6$ | $50$ |
| $6$ | $< 10^{17}$ | $10$ |
| $7$ | $< 10^{17}$ | $10$ |
| $8$ | $< 10^{17}$ | $20$ |
| $9$ | $< 10^{17}$ | $30$ |
| $10$ | $< 10^{17}$ | $50$ |
| $11$ | $< 10^{50}$ | $2$ |
| $12$ | $< 10^{50}$ | $10$ |
| $13$ | $< 10^{100}$ | $2$ |
| $14$ | $< 10^{100}$ | $3$ |
| $15$ | $< 10^{100}$ | $10$ |
| $16$ | $< 10^{200}$ | $3$ |
| $17$ | $< 10^{200}$ | $10$ |
| $18$ | $< 10^{300}$ | $10$ |
| $19$ | $< 10^{300}$ | $10$ |
| $20$ | $< 10^{300}$ | $20$ |
| $21$ | $< 10^{500}$ | $10$ |
| $22$ | $< 10^{500}$ | $20$ |
| $23$ | $< 10^{1000}$ | $30$ |
| $24$ | $< 10^{1000}$ | $50$ |
| $25$ | $< 10^{1000}$ | $50$ |
具体的数据规模与约定见下表。
| 测试点编号 | $R$ | $k$ |
| :--------: | :-----------: | :--: |
| $1$ | $< 10^6$ | $1$ |
| $2$ | $< 10^6$ | $10$ |
| $3$ | $< 10^6$ | $20$ |
| $4$ | $< 10^6$ | $30$ |
| $5$ | $< 10^6$ | $50$ |
| $6$ | $< 10^{17}$ | $10$ |
| $7$ | $< 10^{17}$ | $10$ |
| $8$ | $< 10^{17}$ | $20$ |
| $9$ | $< 10^{17}$ | $30$ |
| $10$ | $< 10^{17}$ | $50$ |
| $11$ | $< 10^{50}$ | $2$ |
| $12$ | $< 10^{50}$ | $10$ |
| $13$ | $< 10^{100}$ | $2$ |
| $14$ | $< 10^{100}$ | $3$ |
| $15$ | $< 10^{100}$ | $10$ |
| $16$ | $< 10^{200}$ | $3$ |
| $17$ | $< 10^{200}$ | $10$ |
| $18$ | $< 10^{300}$ | $10$ |
| $19$ | $< 10^{300}$ | $10$ |
| $20$ | $< 10^{300}$ | $20$ |
| $21$ | $< 10^{500}$ | $10$ |
| $22$ | $< 10^{500}$ | $20$ |
| $23$ | $< 10^{1000}$ | $30$ |
| $24$ | $< 10^{1000}$ | $50$ |
| $25$ | $< 10^{1000}$ | $50$ |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？