← 返回题目列表

Codeforces · 2150/D

D. 吸引力理论

中文机器翻译题面 查看原题
泰勒·斯威夫特 - 爱情故事(泰勒版)
⠀

一维坐标轴上的位置 $$$p_1, p_2, \ldots, p_n$$$ 有 $$$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 \lt x$$$,则人向正方向移动,$$$p_i$$$ 增加$$$1$$$;
  • 如果$$$p_i \gt 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 \le a_i \le 10^9$$$)

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

输出

对于每个测试用例,输出一行包含一个整数:$$$score(p)$$$ 在所有可能的不同位置数组 $$$p$$$ 上的总和,这些数组可能与放置景点有关,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

7
1
1
2
5 10
3
1 1 1
4
1 1 1 1
4
10 2 9 7
5
1000000000 1000000000 1000000000 1000000000 1000000000
8
100 2 34 59 34 27 5 6

输出
复制

1
45
24
72
480
333572930
69365

注意

在第一个测试用例中,唯一可能的结果是该人 $$$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$$$。