34059번 - 해안선 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 286 | 170 | 144 | 63.436% |
문제
$N$개의 도시가 해안선을 따라 원형으로 배치되어 있다. 도시는 시계 방향으로 $1$번부터 $N$번까지 번호가 차례로 붙어 있다. 모든 도시 쌍에 대해, 해당 두 도시를 연결하는 양방향 직선 도로가 존재한다.
이 수많은 도로들 중, $a$번 도시와 $b$번 도시를 잇는 도로를 특별한 도로라고 부른다. 이 특별한 도로는 $1$번 도시가 아닌 두 도시를 이으며, 경치가 가장 아름다운 도로로 알려져 있다.
정서는 다음과 같은 방식으로, 도로만을 이용해 이 도시들을 여행하려 한다.
- 여행은 $1$번 도시에서 출발하며, 출발과 동시에 $1$번 도시는 이미 방문한 것으로 간주한다.
- 여행 중에는 $1$번 도시를 포함한 이미 방문한 도시를 다시 방문해서는 안 되며, 모든 도시를 정확히 한 번씩 방문해야 한다.
- 여행 중 이용하는 어떤 두 도로도 서로 교차하지 않아야 한다.
- 여행 중에는 반드시 특별한 도로를 한 번 이용해야 한다. 단, 특별한 도로를 이용하는 방향은 중요하지 않다.
위 조건을 모두 만족하는 이동 경로의 수를 구하시오.
입력
첫째 줄에 도시의 수 $N$이 주어진다. ($3 \leq N \leq 1\,000\,000$)
둘째 줄에 특별한 도로가 잇는 두 도시의 번호 $a$, $b$가 공백으로 구분되어 주어진다. ($2\leq a, b \leq N$; $a\neq b$)
출력
조건을 만족하는 모든 경로의 수를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.
예제 입력 1
4 2 4
예제 출력 1
2
예제 입력 2
6 5 4
예제 출력 2
11
출처
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2025 예선 H번
- 문제를 만든 사람: isekaijoucho
- 문제를 검수한 사람: 79brue, evenharder, hyperbolic, kipa00, leo020630, ncy09, seonah
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호