← 返回题目列表

AtCoder · pakencamp_2025_day3_i

I. 企鹅闪烁

中文机器翻译题面 查看原题

配点 : 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 选择一项。