← 返回题目列表

Codeforces · 1091/D

D. 新年和排列串联

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

令 $$$n$$$ 为整数。按字典顺序考虑整数 $$$1$$$ 到 $$$n$$$ 的所有排列,并将它们连接成一个大序列 $$$p$$$。例如,如果 $$$n = 3$$$,则 $$$p = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]$$$。该序列的长度将为$$$n \cdot n!$$$。

设 $$$1 \leq i \leq j \leq n \cdot n!$$$ 为一对索引。我们将序列 $$$(p_i, p_{i+1}, \dots, p_{j-1}, p_j)$$$ 称为 $$$p$$$ 的子数组。它的长度定义为其元素的数量,即 $$$j - i + 1$$$。它的总和是其所有元素的总和,即 $$$\sum_{k=i}^j p_k$$$。

你得到了$$$n$$$。求 $$$p$$$ 长度为 $$$n$$$ 且总和为 $$$\frac{n(n+1)}{2}$$$ 的子数组的数量。由于这个数字可能很大,因此输出它对 $$$998244353$$$(质数)取模。

输入

唯一一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$),如问题陈述中所述。

输出

输出一个整数 - 长度为 $$$n$$$ 且总和为 $$$\frac{n(n+1)}{2}$$$ 的子数组的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

3

输出 #1

9

输入 #2

4

输出 #2

56

输入 #3

10

输出 #3

30052700

注意

在第一个示例中,有 $$$16$$$ 长度为 $$$3$$$ 的子数组。按照出现顺序,它们是:

$$$[1, 2, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 3]$$$, $$$[1, 3, 2]$$$, $$$[3, 2, 2]$$$, $$$[2, 2, 1]$$$, $$$[2, 1, 3]$$$, $$$[1, 3, 2]$$$, $$$[3, 2, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 3]$$$, $$$[1, 3, 1]$$$, $$$[3, 1, 2]$$$, $$$[1, 2, 3]$$$, $$$[2, 3, 2]$$$, $$$[3, 2, 1]$$$.

它们的总和为 $$$6$$$、$$$6$$$、$$$7$$$、$$$6$$$、$$$7$$$、$$$5$$$、$$$6$$$、$$$6$$$、$$$8$$$、$$$6$$$、$$$7$$$、$$$5$$$、 $$$6$$$、$$$6$$$、$$$7$$$、$$$6$$$。由于$$$\frac{n(n+1)}{2} = 6$$$,答案是$$$9$$$。