← 返回题目列表

Codeforces · 1601/F

F. 两种

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

从 $$$1$$$ 到 $$$n$$$(含)的整数按字典顺序排序(将整数视为字符串)。结果得到数组$$$a_1, a_2, \dots, a_n$$$。

计算 $$$(\sum_{i = 1}^n ((i - a_i) \mod 998244353)) \mod 10^9 + 7$$$ 的值。

$$$x \mod y$$$ 这里表示 $$$x$$$ 除以 $$$y$$$ 后的余数。该余数始终为非负数,并且不超过 $$$y - 1$$$。例如,$$$5 \mod 3 = 2$$$,$$$(-1) \mod 6 = 5$$$。

输入

第一行包含单个整数 $$$n$$$ ($$$1 \leq n \leq 10^{12}$$$)。

输出

打印一个整数——所需的总和。

示例

输入 #1

3

输出 #1

0

输入 #2

12

输出 #2

994733045

输入 #3

21

输出 #3

978932159

输入#4

1000000000000

输出#4

289817887

注意

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。

例如,$$$42$$$ 按字典顺序小于 $$$6$$$,因为它们的第一位数字不同,并且 $$$4 < 6$$$; $$$42 < 420$$$,因为 $$$42$$$ 是 $$$420$$$ 的前缀。

让我们将 $$$998244353$$$ 表示为 $$$M$$$。

在第一个示例中,数组 $$$a$$$ 等于 $$$[1, 2, 3]$$$。

- $$$(1 - 1) \mod M = 0 \mod M = 0$$$
- $$$(2 - 2) \mod M = 0 \mod M = 0$$$
- $$$(3 - 3) \mod M = 0 \mod M = 0$$$

因此,$$$(0 + 0 + 0) \mod 10^9 + 7 = 0$$$

在第二个示例中,数组 $$$a$$$ 等于 $$$[1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9]$$$。

- $$$(1 - 1) \mod M = 0 \mod M = 0$$$
- $$$(2 - 10) \mod M = (-8) \mod M = 998244345$$$
- $$$(3 - 11) \mod M = (-8) \mod M = 998244345$$$
- $$$(4 - 12) \mod M = (-8) \mod M = 998244345$$$
- $$$(5 - 2) \mod M = 3 \mod M = 3$$$
- $$$(6 - 3) \mod M = 3 \mod M = 3$$$
- $$$(7 - 4) \mod M = 3 \mod M = 3$$$
- $$$(8 - 5) \mod M = 3 \mod M = 3$$$
- $$$(9 - 6) \mod M = 3 \mod M = 3$$$
- $$$(10 - 7) \mod M = 3 \mod M = 3$$$
- $$$(11 - 8) \mod M = 3 \mod M = 3$$$
- $$$(12 - 9) \mod M = 3 \mod M = 3$$$

因此,$$$(0 + 998244345 + 998244345 + 998244345 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) \mod 10^9 + 7$$$ $$$=$$$ $$$2994733059 \mod 10^9 + 7$$$ $$$=$$$ $$$994733045$$$