P15714 [JAG 2023 Summer Camp #2] Distance Permutation

你按照以下方式构造一个长度为 $10^5$ 的排列 $P = (P_1, P_2, \ldots, P_{10^5})$。 数轴上有 $1, 2, \ldots, 10^5$ 这些点。点 $i$ 和点 $j$ 之间的距离是 $|i - j|$。此外，有一个初始为空的序列 $P$。从任意点开始，重复以下操作，直到 $P$ 的长度达到 $10^5$： - 令 $x$ 为当前点对应的数字。如果 $x$ 不在 $P$ 中，则将 $x$ 添加到 $P$ 的末尾。接着，移动到距离当前点小于等于 $K$ 的任意一个点。 回答以下 $Q$ 个查询： - 给定整数 $N, L, R$。令从 $P$ 中移除大于 $N$ 的元素后得到的序列为 $P' = (P'_1, P'_2, \ldots, P'_N)$。在所有可能的 $P'$ 的排列中，回答满足 $P'_1$ 大于等于 $L$ 且小于等于 $R$ 的排列数量，结果对 $998244353$ 取模。

$$ \begin{aligned} &K \ Q \\ &query_1 \\ &\vdots \\ &query_Q \end{aligned} $$ $query_i$ 表示第 $i$ 个查询。 每个查询的格式如下： $$N \ L \ R$$ 输入满足以下约束： - 所有输入均为整数。 - $1 \leq Q \leq 2 \times 10^5$ - $1 \leq K \leq 10^5$ - $1 \leq N \leq 10^5$ - $1 \leq L \leq R \leq N$

输出 $Q$ 行。在第 $i$ 行，输出第 $i$ 个查询的答案。

在样例输入 1 中，对于第一个查询，有四种可能的序列作为 $P'$： - $(1, 2, 3, 4)$ - $(1, 2, 4, 3)$ - $(1, 3, 2, 4)$ - $(1, 3, 4, 2)$ 翻译由 DeepSeek V3.2 完成