#P10009. 黑洞合并

    ID: 8231 传统题 7500ms 512MiB 尝试: 4 已通过: 1 难度: 4 上传者: 标签>CF1500普及+/提高-不变量分析模逆元同余的加减乘运算2024“钉耙编程”中国大学生算法设计超级联赛(9)

黑洞合并

黑洞合并

Problem Description

宇宙中初始有 nn 个黑洞,从左到右编号为 11 到 nn,初始质量依次为 w1,w2,⋯ ,wnw_1, w_2,\cdots, w_n。 黑洞间即将发生 n−1n - 1 次合并,每次将两个黑洞合并为一个。合并遵循的规律如下:

  • 第 ii 次合并开始前,剩余的黑洞数量为 n−i+1n - i + 1,从左到右 重新编号 为 1,2,⋯ ,n−i+11, 2, \cdots, n - i + 1;
  • 第 ii 次合并时,随机 选取两个编号为 xix_i 和 yiy_i ,满足 xi+yi=n−i+2x_i + y_i = n - i + 2 的黑洞进行合并,合并后的黑洞 随机 占据原先黑洞 xix_i 或 yiy_i 的位置,其质量为 wxi+wyiw_{x_i}+w_{y_i};
  • 第 ii 次合并会释放出 wxi⋅wyi⋅(wxi+wyi)w_{x_i} \cdot w_{y_i} \cdot (w_{x_i}+w_{y_i})的能量。 n−1n - 1 次合并后,只剩下一个黑洞,请你计算 n−1n - 1 次合并中释放能量之和的期望。答案可能很大,请输出答案对 998244353 取模后的结果。

Input

输入包含多组测试数据: 输入的第一行包含一个整数 TT (1≤T≤101\leq T\leq 10),表示测试数据的组数。 对于每组测试数据: 第一行包含一个整数 nn (1≤n≤1061\leq n\leq 10^6),表示初始黑洞的数量。 第二行包含 nn 个整数 w1,w2,⋯ ,wnw_1, w_2, \cdots, w_n (1≤wi≤1061\leq w_i\leq 10^6),表示黑洞的初始质量。

Output

对于每组测试数据: 一行包含一个整数,表示答案对 998244353 取模后的结果。

Sample Input

1
3
1 1 1

Sample Output

8

Source

2024“钉耙编程”中国大学生算法设计超级联赛(9)