따스나라의 중계기

조합의 값을 $\binom{n}{r}$로 나타내며, 범위를 벗어난 경우에는 $0$으로 정의한다. 모든 조합은 $998\,244\,353$으로 나눈 나머지로 계산한다.

$D=1$인 경우

지름이 $1$ 이하라는 것은 선택한 모든 중계기 쌍이 직접 통신할 수 있다는 뜻이다.

선택한 중계기 중 높이가 가장 낮은 것들을 생각하자. 그중 가장 왼쪽 중계기의 위치를 $p$로 고정한다. 다른 선택된 위치 $q$는 다음 조건을 만족해야 한다.

• $p<q$이면 $h_q\ge h_p$이고, $$와 가 직접 통신할 수 있다.

왼쪽에서 높이가 같은 위치를 제외하는 이유는 $p$가 가장 왼쪽의 최저 중계기이기 때문이다. 오른쪽에서는 높이가 같은 중계기를 하나 더 선택할 수 있다.

위 조건을 만족하는 위치들 중 아무 위치나 함께 선택해도 전체가 완전 그래프가 된다. 예를 들어 $p<a<b$이고 $p$가 $b$와 직접 통신한다면, $h_b$는 와 사이의 모든 높이보다 크므로 와 도 직접 통신한다. 왼쪽이나 의 양쪽에 위치한 두 중계기에 대해서도 같은 방식으로 확인할 수 있다.

$p$의 오른쪽 후보는 다음과 같은 사슬을 이룬다.

• 처음에는 오른쪽에서 처음 등장하는 높이 $h_p$ 이상의 산으로 이동한다.
• 그 다음부터는 현재 산보다 엄격히 높은 산 중 오른쪽에서 처음 등장하는 산으로 이동한다.

왼쪽 후보는 이전의 엄격히 높은 산을 계속 따라가면 된다. 다음 크거나 같은 원소와 이전 또는 다음의 엄격히 큰 원소는 단조 스택으로 구할 수 있다. 각 사슬의 길이도 점화식으로 계산할 수 있다.

$p$에서 선택 가능한 다른 위치의 수를 $c_p$라 하면, $p$를 기준으로 세는 방법의 수는

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

이다. 모든 $p$에 대해 더하면 된다. 각 설치 방법은 가장 왼쪽의 최저 중계기에 의해 정확히 한 번 세어진다.

$D\ge 2$인 경우

선택한 중계기의 최고 높이를 $H$라 하고, 높이가 $H$인 선택된 위치를

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

이라 하자.

높이가 $H$ 이상인 모든 산을 위치 순서대로 나열한다. $p_1,p_2,\ldots,p_m$은 이 나열에서 연속해야 한다. 사이에 선택되지 않은 높이 이상의 산이 있다면, 그 산을 사이에 두고 양쪽의 어떤 선택된 중계기도 직접 통신할 수 없으므로 그래프가 연결되지 않는다.

이 나열에서 $p_1$의 바로 이전 위치를 $q_0$, $p_m$의 바로 다음 위치를 이라 하자. 존재하지 않으면 각각 , 로 생각한다. 다음 세 수를 정의한다.

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

최고 높이보다 낮은 중계기는 $q_0$과 $q_{m+1}$ 사이에서만 선택할 수 있다. $L$은 첫 최고 중계기의 왼쪽 영역, $$은 마지막 최고 중계기의 오른쪽 영역, 는 최고 중계기들 사이의 내부 영역에 있는 후보 수이다.

최고 중계기 $p_1,p_2,\ldots,p_m$은 순서대로 경로를 이룬다. 내부 영역의 중계기는 양옆의 가까운 최고 중계기에 연결된다. 왼쪽 영역의 중계기는 $$에만, 오른쪽 영역의 중계기는 에만 연결될 수 있다.

왼쪽 영역에서 하나 이상 선택했는지를 $a$, 오른쪽 영역에서 하나 이상 선택했는지를 $b$라 하자. $a,b\in\{0,1\}$이다. $D\ge2$이므로 같은 영역이나 같은 내부 구간에 있는 두 낮은 중계기 사이의 거리 는 자동으로 허용된다. 지름 조건에서 추가로 확인할 값은

$$m-1+a+b$$

이며, 이것이 $D$ 이하여야 한다.

남은 $K-m$개의 중계기를 고르는 방법은 다음과 같다.

• $m\le D-1$이면 양쪽 바깥 영역을 모두 사용해도 된다. $\binom{L+I+R}{K-m}$

이제 모든 가능한 최고 중계기 구간을 열거한다. 산을 높이 내림차순으로 처리하면서, 현재 높이 이상의 산 위치를 순서 집합에 저장한다. 같은 높이의 위치는 한꺼번에 삽입한다. 순서 집합에서 현재 높이의 위치들이 이루는 각 연속 구간마다 길이 $D+1$ 이하의 모든 부분 구간을 열거한다. 각 부분 구간이 하나의 $p_1,\ldots,p_m$ 후보가 된다.

각 위치는 왼쪽 끝점으로 최대 $D+1$개의 구간만 만든다. 따라서 시간 복잡도는 테스트 케이스마다

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

이고, 메모리 복잡도는 $O(N)$이다. $D=1$인 경우의 시간 복잡도는 $O(N)$이다.

Solution written by GPT5.6