← 返回题目列表

Codeforces · 1073/E

E. 段总和

中文机器翻译题面 查看原题

给定两个整数 $$$l$$$ 和 $$$r$$$ ($$$l \le r$$$)。您的任务是计算从 $$$l$$$ 到 $$$r$$$(包括 $$$l$$$ 和 $$$r$$$)的数字总和,使得每个数字最多包含 $$$k$$$ 个不同的数字,并以 $$$998244353$$$ 为模打印该总和。

例如,如果 $$$k = 1$$$,那么您必须计算从 $$$l$$$ 到 $$$r$$$ 的所有数字,以便每个数字仅使用一位数字组成。对于$$$l = 10,r = 50$$$,答案是$$$11 + 22 + 33 + 44 = 110$$$。

输入

输入的唯一行包含三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$ ($$$1 \le l \le r < 10^{18}, 1 \le k \le 10$$$) — 段的边界和不同数字的最大数量。

输出

打印一个整数 - 从 $$$l$$$ 到 $$$r$$$ 的数字之和,使得每个数字最多包含 $$$k$$$ 个不同的数字,以 $$$998244353$$$ 为模。

示例

输入 #1

10 50 2

输出 #1

1230

输入 #2

1 2345 10

输出 #2

2750685

输入 #3

101 154 2

输出 #3

2189

注意

对于第一个示例,答案只是从 $$$l$$$ 到 $$$r$$$ 的数字之和,等于 $$$\frac{50 \cdot 51}{2} - \frac{9 \cdot 10}{2} = 1230$$$。此示例也在问题陈述中进行了解释,但对于 $$$k = 1$$$。

对于第二个示例,答案只是从 $$$l$$$ 到 $$$r$$$ 的数字之和,等于 $$$\frac{2345 \cdot 2346}{2} = 2750685$$$。

对于第三个示例,答案为 $$$101 + 110 + 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 + 121 + 122 + 131 + 133 + 141 + 144 + 151 = 2189 美元。