CF2150D.Attraction Theory

Taylor Swift - Love Story (Taylor's Version)

⠀

有 $n$ 个人分别站在一维坐标轴上的 $p_1, p_2, \ldots, p_n$ 位置上。初始时对于每个 $1 \leq i \leq n$，有 $p_i = i$。

你可以在某个整数坐标 $x$（$1 \le x \le n$）设置一次“景点”，然后所有人都会向景点靠拢去观赏。

具体地，如果你在 $x$ 位置设置景点（$1 \le x \le n$），那么每个人 $i$（$1 \le i \le n$）的位置会发生如下变化：

• 如果 $p_i = x$，位置不变；
• 如果 $p_i < x$，此人向正方向走一步，$p_i$ 增加 $1$；
• 如果 $p_i > x$，此人向负方向走一步，$p_i$ 减少 $1$。

你可以以任意顺序、次数设置景点。

可以证明，所有人的位置始终都在区间 $[1, n]$ 内，即 $1 \le p_i \le n$ 始终成立。

每个位置 $x$（$1 \le x \le n$）都对应一个数值 $a_x$。一个位置数组 $[p_1, p_2, \ldots, p_n]$ 的得分 $score(p)$ 为 $\sum_{i = 1}^{n} a_{p_i}$，即每个人最后所在的位置 $x$ 会让你的得分增加 $a_x$。

对于通过任意方式设置景点，所有可能出现的不同位置数组 $p$，求 $score(p)$ 之和。由于答案可能很大，请对 $998\,244\,353$ 取模后输出。

每组测试数据包含多组测试用例。第一行输入测试用例数 $t$（$1 \le t \le 10^4$）。
接下来的每组测试用例输入如下：

每组测试用例第一行输入一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

第二行输入 $n$ 个整数——$a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）。

保证所有测试用例中 $n$ 的和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出一行一个整数，表示通过任意设置景点后，所有可能出现的不同位置数组 $p$ 的 $score(p)$ 之和，模 $998\,244\,353$。

在第一个测试用例中，唯一的可能是第 1 个人一直在位置 1，得分为 $a_1 = 1$。

在第二个测试用例中，可能出现的位置数组 $[p_1, p_2]$ 为：

• $[1, 2]$，得分为 $15$；
• $[1, 1]$，得分为 $10$；
• $[2, 2]$，得分为 $20$。

所有得分之和为 $15 + 10 + 20 = 45$。

在第三个测试用例中，可能出现的位置数组 $[p_1, p_2, p_3]$ 为：

• $[1, 1, 1]$；
• $[1, 1, 2]$；
• $[1, 2, 2]$；
• $[1, 2, 3]$；
• $[2, 2, 2]$；
• $[2, 2, 3]$；
• $[2, 3, 3]$；
• $[3, 3, 3]$。

每组得分为 $3$，因此总和为 $24$。

由 ChatGPT 5 翻译