zyxzyx100219 @ 2024-11-28 13:39:48
题目描述
有 𝑛 堆果子，分别有 𝑎1 , 𝑎2 , ⋯ , 𝑎𝑛 个果子。一次合并分为有顺序的 𝑛 − 1 步，每一步选择两堆果子，合并成一堆。
定义一次合并的权值为每一步被合并的两堆果子数量之积的和。求出每一种合并方法的权值之和对998244353取模的结果。
两种合并方式不同当且仅当有一步被合并的两堆不同。即使有两堆的果子数量相同，我们仍然把它们视为不同的两堆。
输入格式
第一行一个正整数 𝑛。 第二行 𝑛 个非负整数，依次表示 𝑎1 , ⋯ , 𝑎𝑛。
输出格式
一行一个非负整数，表示所有合并方法权值之和（对 998244353 取模）。
样例
样例输入1 2
100001 100002
样例输出1
17856472
样例解释1
只能合并 1 步，即合并仅有的两堆。 两堆果子数量之积为 100001 ∗ 100002 = 10000300002， 对 998244353 取模的结果为 17856472。
注意合并 (𝐴, 𝐵) 和 (𝐵, 𝐴) 视为相同的合并方式。
样例输入2
3
1 2 3
样例输出2
33
by zyxzyx100219 @ 2024-11-28 13:40:55
方案数推错了
by zyxzyx100219 @ 2024-11-28 13:41:31
错误方案数：n!/2
by zyxzyx100219 @ 2024-11-28 13:42:16
球正确方案数QAQ
by Mr_Az @ 2024-11-28 14:17:37
合并果子，自己搜
by zyxzyx100219 @ 2024-11-28 14:29:47
@Mr_Az 不一样吧
by chen_z @ 2024-11-28 14:46:10
@zyxzyx100219 是不一样
by zyxzyx100219 @ 2024-11-28 15:15:45
f(1)=1; f(2)=1; f(3)=3; f(4)=18; f(5)=120???
by Mr_Az @ 2024-11-28 15:20:10
n的范围
by Mr_Az @ 2024-11-28 15:29:16
@zyxzyx100219 A109714
by zyxzyx100219 @ 2024-11-28 15:30:29
@Mr_Az 10的5次方