P7493 [Chuanzhi Cup #3 Finals] Traveler 1969

In the 21st century, which is called the future, only unease and a little fantasy remain. O sinners of eternity and instant, the Noah's Ark of the 20th century carries expectations and unease and flies toward the sky! And you, as hope, on this journey that is not eternal, how will you move forward?

On a straight road, there are $n$ hotels. The coordinate of the $i$-th hotel is $i$. Every morning, you start from a hotel and can walk a maximum distance of $m$. You are also given a fixed constant $k$. You are given $q$ queries. In each query, given $u, v$, find the number of plans to start in the morning from hotel $u$ to hotel $v$, passing through at most $k$ hotels (excluding the start point $u$) and keeping the walking direction unchanged. Two plans are different if and only if there exists a different choice of a hotel. The answer should be taken modulo $998244353$. For all testdata, $n, q \leq 10^5$, $m, k \leq 10^4$, $mk \leq 10^5$, and $u, v \leq n$.

The input has $q + 1$ lines. The first line contains $4$ positive integers $n, m, k, q$. The next $q$ lines each contain $2$ positive integers $u, v$, representing a query.

Output $q$ lines, each containing $1$ integer, representing the answer.

Translated by ChatGPT 5