配点 : 100 点
問題文
旁边有一个长长的溜冰场。溜冰场 它从左侧开始分为 L+2 部分。 它的编号为 0,1,2,\dots,L,L+1 。隔间 0 和分区 已授予使用 L+1 有一个洞掉进海里,其他部分没有洞。
在溜冰场没有洞的区域中,N 地段有企鹅。i 企鹅被分割 你在 P_i ,有企鹅的部分都不同。
海雀帕塔罗现在将移动企鹅,直到所有企鹅落入海中。具体来说,执行以下操作,直到所有企鹅落入海中。
- 随机化没有落入海中的企鹅。 1 选择一项。
- 随机选择向左或向右,然后将其向所选方向移动。企鹅会继续朝指定方向移动,直到满足以下条件之一:
- 到达有另一只企鹅的隔间之前的隔间。
- 到达一个有洞的区域并掉进海里。
但是,假设掉入海中的企鹅不在任何部分。此外,所有选择都是独立做出的。
企鹅 1 操作中的分区 当企鹅移动到 i 分区 移至 j 时,计算企鹅这次操作移动的距离。 比方说 |i-j| 。所有企鹅直到落入海中为止所经过的总距离的预期值。 打印第 \bmod 998244353 找到它。
以上问题 请解决 T 测试用例。
制約
- 1\leq T\leq 100
- 1\leq N\leq 5000
- N\leq L\leq 10^9
- 1\leq P_1\lt P_2\lt \dots \lt P_N\leq L
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出。 打印
N L P_1 P_2 \dots P_N
出力
T 行。
i 行中,i 个测试用例的答案。具体来说,可以证明期望的期望值始终是有理数,并且在该问题的约束下,该值可以表示为相对素的正整数。 p,q 可以表示为 \frac{p}{q} 时表示为r\times q\equiv p \pmod{998244353} 和 0\leq r\lt 998244353 整数 r 仅仅是 1 因为我们可以证明有两个 在第 r 。
入力例 1
3 1 8 2 4 7638 7 66 333 888 5 21 2 4 9 15 17
出力例 1
499122181 308996191 485077673
1 个测试用例中,Pataro 1 当你向左移动企鹅时,它移动的距离是 2 如果向右移动,移动的距离将为 7 不管怎样,企鹅都会掉进海里。因此,出行距离的期望值为 在第 \frac{9}{2} 。499122181 \times 2\equiv9\pmod{998244353} 所以答案是 499122181 。
2 个测试用例中,例如,Patar 首先 如果将第 4 只企鹅移到左边,4 企鹅被分割 你在 334 ,此时行驶的距离为 554 。当然,除此之外还有多种移动企鹅的方式,而帕塔罗都是随机的。 由 1 选择一项。