DOJ

해설

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

$D=1$ 인 경우

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

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

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

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

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

$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$ 은 이 나열에서 연속해야 한다. 사이에 선택되지 않은 높이 $H$ 이상의 산이 있다면, 그 산을 사이에 두고 양쪽의 어떤 선택된 중계기도 직접 통신할 수 없으므로 그래프가 연결되지 않는다.

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

\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$ 은 첫 최고 중계기의 왼쪽 영역, $R$ 은 마지막 최고 중계기의 오른쪽 영역, $I$ 는 최고 중계기들 사이의 내부 영역에 있는 후보 수이다.

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

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

m-1+a+b

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

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

$m\le D-1$ 이면 양쪽 바깥 영역을 모두 사용해도 된다. $\binom{L+I+R}{K-m}$
$m=D$ 이면 양쪽 바깥 영역을 동시에 사용하면 안 된다. $\binom{I+R}{K-m}+\binom{L+I}{K-m}-\binom{I}{K-m}$
$m=D+1$ 이면 두 바깥 영역을 모두 사용하면 안 된다. $\binom{I}{K-m}$
$m>D+1$ 이면 불가능하다.

이제 모든 가능한 최고 중계기 구간을 열거한다. 산을 높이 내림차순으로 처리하면서, 현재 높이 이상의 산 위치를 순서 집합에 저장한다. 같은 높이의 위치는 한꺼번에 삽입한다. 순서 집합에서 현재 높이의 위치들이 이루는 각 연속 구간마다 길이 $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

따스나라의 중계기

해설