409297: GYM103480 D 转动命运之轮

$$$n$$$ 个小朋友站成一排，他们都有一个属于他们的玩具，每个小朋友具有开心值 $$$h_i$$$。

对于任意玩具都带有唯一的标号，$$$i$$$ 号小朋友的玩具标号为 $$$i$$$，不幸的是，现在这些玩具被随机分配给了这 $$$n$$$ 个小朋友。

对于某种分配下，小朋友 $$$i$$$ 会首先观察拿到的玩具的标号，记为 $$$w_i$$$。

下面会进行若干轮操作，每轮操作后小朋友 $$$i$$$ 会观察此时他的玩具标号 $$$p_i$$$，并将这个玩具给小朋友 $$$w_i$$$。

经过此轮操作后，若发现某个小朋友 $$$i$$$ 的玩具恰好等于初始拿到的玩具标号，即 $$$p_i = w_i$$$，则该小朋友不再进行接下来的所有操作。

定义总开心值为每个小朋友的开心值乘一共经历的轮数的和，形式化表达：

$$$$$$ H = \sum_{i=1}^n h_i \times c_i $$$$$$

其中 $$$H$$$ 表示总开心值，$$$c_i$$$ 表示经历的操作轮数。

现在定义 $$$U_n$$$ 为长度 $$$n$$$ 的排列的全集，你需要输出：

$$$$$$ \sum_{P \in U_n} H_P $$$$$$

输入第一行 $$$n$$$ 表示排列的长度 $$$(1 \leq n \leq 2000)$$$。

接下来 $$$n$$$ 个数，其中第 $$$i$$$ 个数表示 $$$i$$$ 号小朋友的开心值 $$$h_i(1 \leq h_i \leq 10^9)$$$。

输出一个数字 $$$ans$$$ 表示答案，由于答案可能会很大，您只需要输出 $$$ans $$$ 取模 $$$998244353$$$ 后的结果。

1
2

2

3
1 1 1

36

5
11 4 5 1 4

9000

当 $$$n = 3$$$ ,开心值 $$$1,1,1$$$ ,排列为 $$$\{3,1,2\}$$$ 时,小朋友会观察他们拿到的玩具标号,有 $$$w_1 = 3,w_2 = 1,w_3 = 2$$$

第一轮操作后,再次观察标号,有 $$$p_1 = 1,p_2 = 2,p_3 = 3$$$

第二轮操作后,再次观察标号,有 $$$p_1 = 2,p_2 = 3,p_3 = 1$$$

第三轮操作后,再次观察标号,有 $$$p_1 = 3,p_2 = 1,p_3 = 2$$$，发现此时满足 $$$w_1 = p_1,w_2 = p_2,w_3 = p_3$$$，三个小朋友不再进行操作,三人经历的轮数都是 $$$3$$$ ,可以算出 $$$H = 1 \cdot 3 + 1 \cdot 3 + 1 \cdot 3 = 9$$$

类似可以得到排列为 $$$\{1,2,3\}$$$ ,$$$\{1,3,2\}$$$ ,$$$\{2,1,3\}$$$ ,$$$\{2,3,1\}$$$ ,$$$\{3,1,2\}$$$ 时的 $$$H$$$ ,对他们求和就可以得到 $$$ans = 36$$$

对于取模我们通常有如下结论

$$$$$$ \begin{aligned} (x + y) \bmod M &= (x \bmod M + y \bmod M) \bmod M \\ (x \cdot y) \bmod M &= ((x \bmod M) \cdot (y \bmod M)) \bmod M \end{aligned} $$$$$$

符号 $$$\sum$$$ 表示求和，如可以用 $$$\sum_{i=1}^{100} i$$$ 表示 $$$1$$$ 到 $$$100$$$ 的求和，即：

$$$$$$ 1 + 2 + 3 + \cdots + 100 $$$$$$

在本题中，可以理解为对所有满足 $$$P \in U_{n}$$$ 的集合 $$$P$$$ 进行求和。