P17300 [ICPC 2026 Xi'an I] Transform

Yuki 有一个大小为 $n$ 的可重集合 $S = \{s_1, \dots, s_n\}$ 和一个整数 $k$。 Yuki 定义一次变换为： - 选择 $S$ 的一个子集 $S'$（$S'$ 可以为空集），将 $S'$ 从 $S$ 中删除，并将 $S'$ 的 $\operatorname{mex}^\ast$ 添加到 $S$ 中。 现在，Yuki 想进行若干次变换，使得 $S$ 变为 $\{k\}$。你需要帮助 Yuki 求出，使 $S$ 变为 $\{k\}$ 所需的最小变换次数。由于答案可能很大，你只需要输出答案对 $998244353$ 取模的结果即可。 可以证明，一定存在至少一种操作方案能够使 $S$ 变为 $\{k\}$。 $^\ast$：一个可重集的 $\operatorname{mex}$ 为该可重集中未出现过的最小非负整数，例如 $\operatorname{mex}\{0,1,2\} = 3$，$\operatorname{mex}\{1,0,3,1\} = 2$，$\operatorname{mex} \varnothing = 0$。

本题包含多组测试数据。 第一行包含一个正整数 $t$ $(1 \le t \le 10^5)$，表示测试数据组数。 对于每组测试数据： - 第一行包含两个整数 $n, k$ $(1 \le n \le 5\cdot10^5,\ 0 \le k \le 10^9)$。 - 第二行包含 $n$ 个整数 $s_1, \dots, s_n$ $(0 \le s_i \le 10^9)$。 保证所有测试数据中 $n$ 的总和不超过 $5\cdot 10^5$。

对于每组测试数据，输出一行，包含一个整数，表示使 $S$ 变为 $\{k\}$ 所需的最小变换次数对 $998244353$ 取模的结果。

对于第 $1$ 组测试数据： - Yuki 可以在第 $1$ 次变换中选择 $S' = \varnothing$，使 $S$ 变为 $\{0,1\}$，再在第 $2$ 次变换中选择 $S' = \{0,1\}$，使 $S$ 变为 $\{2\}$。 - 可以证明，不存在变换次数更少的操作方案，因此答案为 $2$。 对于第 $2$ 组测试数据： - Yuki 不需要进行变换即可使 $S = \{4\}$，因此答案为 $0$。 对于第 $3$ 组测试数据： - Yuki 可以在第 $1$ 次变换中选择 $S' = \varnothing$，使 $S$ 变为 $\{0,0,2,2\}$，在第 $2$ 次变换中选择 $S' = \{0,2\}$，使 $S$ 变为 $\{0,1,2\}$，再在第 $3$ 次变换中选择 $S' = \{0,1,2\}$，使 $S$ 变为 $\{3\}$。 - 可以证明，不存在变换次数更少的操作方案，因此答案为 $3$。 对于第 $4$ 组测试数据： - Yuki 可以在第 $1$ 次变换中选择 $S' = \{2,3\}$，使 $S$ 变为 $\{0,0,1\}$，再在第 $2$ 次变换中选择 $S' = \{0,0,1\}$，使 $S$ 变为 $\{2\}$。 - 可以证明，不存在变换次数更少的操作方案，因此答案为 $2$。 对于第 $5$ 组测试数据： - Yuki 可以直接在第 $1$ 次变换中选择 $S' = \{0,1,2,2\}$，使 $S$ 变为 $\{3\}$。 - 可以证明，不存在变换次数更少的操作方案，因此答案为 $1$。