Relay Stations in the Mountains

Write combinations as $\binom{n}{r}$, and define the value as $0$ when $r$ is outside $[0,n]$. All combination values are computed modulo $998\,244\,353$.

Case $D=1$

Diameter at most $1$ means that every selected pair must communicate directly.

Fix a selected position $p$ that is the leftmost among the minimum-height selected positions. Every other selected position $q$ must satisfy the following conditions.

• If $p<q$, then $h_q\ge h_p$ and $$ communicate directly.

An equal-height position on the left is forbidden because $p$ is the leftmost minimum. One equal-height position on the right may still be selected.

Any subset of these candidate positions forms a clique together with $p$. For example, if $p<a<b$ and $p$ communicates directly with $b$, then $h_b$ is larger than every height strictly between and . Therefore and also communicate directly. The other relative orders are proved similarly.

The candidates to the right form a chain. First move to the nearest position on the right whose height is at least $h_p$. Afterwards, repeatedly move to the nearest strictly greater position on the right. The candidates to the left are obtained by repeatedly moving to the previous strictly greater position.

Nearest greater-or-equal and nearest strictly greater positions are found with monotone stacks. The chain lengths are then computed by simple recurrences.

If $c_p$ candidate positions are available for a fixed $p$, they contribute

$$\binom{c_p}{K-1}.$$

Every valid installation is counted exactly once by its leftmost minimum-height relay.

Case $D\ge2$

Let $H$ be the maximum selected height, and let the selected positions of height $H$ be

$$p_1<p_2<\cdots<p_m.$$

List all positions whose height is at least $H$ in increasing order. The positions $p_1,\ldots,p_m$ must be consecutive in this list. Otherwise, an unselected mountain of height at least $H$ lies between two selected sides and blocks every possible edge across it, so the graph is disconnected.

Let $q_0$ be the previous position before $p_1$ in this list, and let $q_{m+1}$ be the next position after . Use and when the corresponding position does not exist. Define

$$\begin{align*} L &= p_1-q_0-1,\\ I &= p_m-p_1-m+1,\\ R &= q_{m+1}-p_m-1. \end{align*}$$

All lower selected relays must lie between $q_0$ and $q_{m+1}$. The values $L$, $$, and count candidates in the left outer region, the internal regions between maximum relays, and the right outer region.

The maximum relays form the path $p_1,p_2,\ldots,p_m$. A relay in an internal gap is adjacent to the neighboring maximum relays. A relay in the left outer region can attach only to , and a relay in the right outer region can attach only to .

Let $a$ and $b$ indicate whether at least one relay is selected from the left and right outer regions. Since $D\ge2$, distances of at most $2$ inside one region require no special handling. The relevant longest path has length

$$m-1+a+b,$$

which must not exceed $D$.

Therefore, after fixing the $m$ maximum relays, the number of ways to choose the remaining $K-m$ relays is as follows.

• If $m\le D-1$, both outer regions may be used: $\binom{L+I+R}{K-m}.$

It remains to enumerate every possible block of maximum relays. Process mountains in decreasing order of height and maintain an ordered set containing positions whose height is at least the current height. Insert all positions of one equal-height group simultaneously. In every consecutive run of the current height in the ordered set, enumerate all contiguous subarrays of length at most $D+1$.

Each position is the left endpoint of at most $D+1$ enumerated blocks. The time complexity per test case is

$$O(N\log N+ND),$$

and the memory complexity is $O(N)$. The $D=1$ case takes $O(N)$ time.

Solution written by GPT5.6