P13606 [NWRRC 2022] IQ Game

一档受欢迎的电视节目“Kak? Zachem? Pochemu?”中，有六名选手组成的团队协作解答各种难题。选手们围坐在一个被分为 $n$ 个扇区的圆桌旁，扇区顺时针编号为 $1$ 到 $n$。游戏开始时，每个扇区上都放有一个信封，里面装有一道需要解答的问题。 每一轮，桌子中央的陀螺会等概率随机选择一个扇区。如果被选中的扇区上有信封，主持人就会打开它并读出里面的问题。如果该扇区没有信封，主持人会顺时针方向打开下一个有信封的扇区。每轮结束后，打开过的信封会被移除。 今晚，观众最喜欢的团队正在参赛。他们已经完成了 $n-k$ 轮，还剩下 $k$ 个信封在桌上。情况对他们来说并不乐观——再答错一道题他们就会被淘汰。其中有一道题是特别难的“Hyperblitz”问题，团队有信心能答对剩下的所有问题，除了“Hyperblitz”。请你计算他们还能继续进行的期望轮数（包括必然会遇到的“Hyperblitz”那一轮），并对 $998\,244\,353$ 取模（具体见输出格式）。

第一行包含三个整数 $n$、$k$ 和 $s$，分别表示扇区总数、剩余信封数，以及“Hyperblitz”问题所在的扇区编号（$1 \le n \le 10^9$；$1 \le k \le \min(n, 200)$；$1 \le s \le n$）。保证 $n \ne 998\,244\,353$。 第二行包含 $k$ 个不同的整数 $q_1, q_2, \ldots, q_k$，表示当前仍有信封的扇区编号，按顺时针顺序排列（$1 \le q_1 < q_2 < \ldots < q_k \le n$）。 其中恰有一个 $i$ 满足 $q_i = s$。

输出一个整数，表示团队还能继续进行的期望轮数（包括必然会遇到的“Hyperblitz”那一轮），对 $998\,244\,353$ 取模。 形式化地说，设 $M = 998\,244\,353$。可以证明，期望轮数可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not\equiv 0 \pmod{M}$。请输出 $p \cdot q^{-1} \bmod M$。也就是说，输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

在第一个样例中，第一轮有 $\frac{1}{3}$ 的概率遇到“Hyperblitz”，因此有 $\frac{1}{3}$ 的概率只进行 1 轮，有 $\frac{2}{3}$ 的概率进行 2 轮。期望轮数为 $1 \cdot \frac{1}{3} + 2 \cdot \frac{2}{3} = \frac{5}{3}$。 由于 $3^{-1} \bmod 998\,244\,353 = 332\,748\,118$，所以正确输出为 $5 \cdot 332\,748\,118 \bmod 998\,244\,353 = 665\,496\,237$。 由 ChatGPT 4.1 翻译