P15998 [ICPC 2020 NAC] All Kill

你刚刚和你的朋友参加完一场编程竞赛。不幸的是，你们未能 AK（即解决所有问题），但现在你想知道是否可能存在某种策略，使得你们能够解决所有问题。 解决一道问题分为两个阶段：思考阶段和编码阶段。你的朋友负责所有思考，而你负责所有编码。 对于每道问题，你已精确计算出自己编码所需的时间。然而，在比赛中编码一道问题之前，你的朋友需要先想出其解法。你无法估计朋友想法的产生时间，因此你采用如下模型：对于每道问题，你的朋友在比赛期间的某个随机分钟产生解题思路，且每个问题对应的这一时刻是独立的均匀随机变量。你一次只能编码一道题，因此任何时刻可能有多个问题在排队。你总是优先编码编号较小的问题。这个过程是按分钟执行的，因此如果在完成编码编号较大的问题之前，朋友想出了编号较小的问题的解法，你就会切换去编码编号较小的问题，但你并不希望这样。上下文切换是一种开销很大的操作，即使是在人脑中！ 比赛策略可按如下方式按分钟建模： - 对于每个尚未有思路的问题，你的朋友在每一分钟有 $1/(\text{比赛剩余分钟数})$ 的概率想出解法。你的朋友可能在同 1 分钟内想出多个问题的解法。 - 在那些仍需编码且朋友已想出解法的题目中，你会选择编号最小的一个，并花下一分钟对其进行编码（如果没有符合条件的题目，则此步骤什么也不做）。 你想要计算以下两个事件同时发生的概率： - 你们的队伍在比赛结束时完成了所有问题的编码； - 对于每个问题，其编码时间构成一个连续的区间。 记该概率为 $p$，$n$ 为比赛中的题目数量，$t$ 为比赛的总分钟数。可以证明 $p \cdot t^n$ 是一个整数。输出 $(p \cdot t^n) \bmod 998,244,353$。注意 $998,244,353$ 是一个大素数。

输入的第一行包含两个空格分隔的整数 $n$（$1 \le n \le 10^5$）和 $t$（$1 \le t \le 10^8$），分别表示比赛中的题目数量和比赛的总分钟数。 接下来的 $n$ 行，每行包含一个整数 $x$（$1 \le x \le 10^3$），按顺序给出每道题的编码时间（以分钟为单位）。保证这些时间的总和不超过 $t$。

输出一个整数，即 $(p \cdot t^n) \bmod 998,244,353$，其中 $p$ 是上述两个事件同时发生的概率。

翻译由 DeepSeek V3.2 完成