30362번 - Distance Permutation 다국어

You construct a permutation $P = (P_1, P_2, \dots , P_{10^5})$ of length $10^5$ in the following way.

The number line has points $1, 2, \dots, 10^5$. The distance between points $i$ and $j$ is $|i-j|$. Also, there is a sequence $P$ that is initially empty. Repeat the following operations from any point until the length of $P$ is $10^5$.

• Let $x$ be the number corresponding to the current point. if $x$ is not in $P$, add $x$ to the end of $P$. Next, move to one of the points whose distance is less than or equal to $K$.

Answer the following $Q$ queries.

You are given integers $N$, $L$, $R$. Let the sequence created by removing elements larger than $N$ from $P$ be $P' = (P'_1, P'_2, \dots , P'_N)$. Among the possible permutations of $P'$, answer the number of permutations in which $P'_1$ is greater than or equal to $L$ and less than or equal to $R$ with $998244353$.

$K$ $Q$

$\text{query}_1$

$\vdots$

$\text{query}_Q$

$\text{query}_i$ represents the $i$-th query.

Each query is given in the following format.

$N$ $L$ $R$

Output $Q$ lines. On the $i$-th line, output the answer of the $i$-th query.

• All inputs consist of integers.
• $1 \le Q \le 2 \times 10^5$
• $1 \le K \le 10^5$
• $1 \le N \le 10^5$
• $1 \le L \le R \le N$

In Sample Input 1, There are four possible sequences as $P'$ in the first query.

• $(1, 2, 3, 4)$
• $(1, 2, 4, 3)$
• $(1, 3, 2, 4)$
• $(1, 3, 4, 2)$