分数: 600 点
问题陈述
有 K 数轴上的机器人。的 i第机器人 (1 \leq i \leq K) 最初位于坐标处 x_i.
以下过程将完全发生 N 次。
- 每个机器人以概率选择移动或不移动 \frac{1}{2} 每个。移动的机器人将 同时 走的距离 1 正方向,其他机器人将保持静止。
在这里,所有概率决策都是独立的。
求没有两个机器人相遇的概率,即在整个程序中,永远不会有两个或多个机器人同时处于同一坐标,模 998244353 (见注释)。
注释
可以证明所讨论的概率始终是有理数。此外,在该问题的约束条件下,当该值表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,可以证明唯一存在一个整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。找到这个 R.
约束
- 2 \leq K \leq 10
- 1 \leq N \leq 1000
- 0 \leq x_1 \lt x_2 \lt \cdots \lt x_K \leq 1000
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
K N x_1 x_2 \ldots x_K
输出
打印答案。
示例输入 1
2 2 1 2
示例输出 1
374341633
所讨论的概率是 \frac{5}{8}.
我们有 374341633 \times 8 \equiv 5\pmod{998244353},所以你应该打印 374341633.
示例输入 2
2 2 10 100
示例输出 2
1
有问题的概率可能是 1.
示例输入 3
10 832 73 160 221 340 447 574 720 742 782 970
示例输出 3
553220346