Apricot Rules LLC는 새로운 단순화된 네트워킹 프로토콜을 개발 중이며, 자신들의 라우팅 알고리즘을 과시하고 싶어 한다. 그들의 설계에서 네트워크는 1번부터 \mathbf{M}번까지 번호가 매겨진 \mathbf{M}대의 기계로 이루어져 있고, 모든 기계 쌍은 직접 링크로 연결되어 있다. 각 링크에는 1 이상 (\mathbf{M} \times (\mathbf{M} - 1) / 2) 이하의 서로 다른 정수 우선순위(priority)가 하나씩 부여되며, 각 기계는 그 우선순위에 따라 트래픽을 라우팅한다.

불행히도 그 라우팅 알고리즘은 너무 공격적이라, 각 기계에서 나가는 모든 트래픽을 그 기계에 연결된 링크 중 우선순위가 가장 높은 링크 하나로만 보내 버린다. 그 결과 어떤 기계 집합들은 다른 집합과 고립될 수 있다.

형식적으로, 기계 m이 링크 \ell을 사용한다는 것은(그리고 그 경우에만) \ell이 m에 연결된 링크들 중 우선순위가 가장 높은 링크라는 뜻이다. 또한 어떤 링크가 활성(active)이라는 것은, 그 링크가 연결하는 두 기계 중 적어도 하나에 의해 사용된다는 뜻이다. 링크 우선순위가 주어지면, 원래 네트워크는 서로 겹치지 않는 여러 인트라넷(intranet)으로 분리된다. 두 기계가 같은 인트라넷에 속하는 것은, 활성 링크만을 사용해 두 기계 사이에 어떤 경로가 존재할 때 그리고 그때뿐이다.

Example with 2 intranets. Active edges are (1, 2) and (3, 4) with weights 6 and 5 respectively. Example with 1 intranet. Active edges are (1, 2), (2, 3), and (3, 4) with weights 6, 5, and 4 respectively.

예를 들어 위의 왼쪽 그림에서는, 우선순위가 6과 5인 링크만 활성이다. 이로 인해 서로 분리된 인트라넷이 두 개 생긴다. 반면 오른쪽 그림에서는 세 개의 링크가 활성이고, 그 결과 4대의 모든 기계가 하나의 인트라넷을 이룬다.

Apricot Rules LLC의 품질 보증 팀의 일원으로서, 당신은 문제의 심각도를 조사하고 있다. 당신은 링크 우선순위가 가능한 (\mathbf{M} \times (\mathbf{M} - 1) / 2)!가지 배정 방법 중에서 균등 무작위로 배정될 때, 인트라넷의 개수가 정확히 \mathbf{K}개일 확률을 알고 싶다.

#10434 upload 1 done 1 how_to_reg 1

인트라넷 timer 20s memory 1024MB

#10434

인트라넷 20s 1024MB