AT_abc216_h [ABC216H] Random Robots

题目描述

在数轴上有 $K$ 个机器人。第 $i$ 个机器人（$1 \leq i \leq K$）最初位于坐标 $x_i$。

接下来将恰好进行 $N$ 次如下操作：

• 对于每个机器人，以概率 $\frac{1}{2}$ 决定“前进”或“停止”。被判定为“前进”的机器人同时向正方向移动 $1$，被判定为“停止”的机器人则保持原地不动。

所有概率性的决策都是独立进行的。

在这一系列操作中，求从未有多个机器人相遇（即任意时刻没有 $2$ 个或以上的机器人处于同一坐标）的概率，答案对 $998244353$ 取模（见注释）。

输入格式

输入通过标准输入按以下格式给出。

$K$ $N$ $x_1$ $x_2$ $\ldots$ $x_K$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 2
1 2

输出 #1

374341633

输入输出样例 #2

输入 #2

2 2
10 100

输出 #2

1

输入输出样例 #3

输入 #3

10 832
73 160 221 340 447 574 720 742 782 970

输出 #3

553220346

说明/提示

注释

可以证明，所求概率一定是有理数。在本题的约束下，设其化为最简分数 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

约束条件

• $2 \leq K \leq 10$
• $1 \leq N \leq 1000$
• $0 \leq x_1 < x_2 < \cdots < x_K \leq 1000$
• 输入均为整数

样例解释 1

所求概率为 $\frac{5}{8}$。$374341633 \times 8 \equiv 5 \pmod{998244353}$，因此输出 $374341633$。

样例解释 2

所求概率有时也可能为 $1$。

由 ChatGPT 4.1 翻译