27474번 - 팬케이크 탑 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.7 초 (추가 시간 없음) | 1024 MB | 90 | 16 | 9 | 20.455% |
문제
팬케이크 애호가 KSA 학생들은 $N$$(N$은 홀수$)$개의 팬케이크를 쌓아서 팬케이크 탑을 만들었다. 그런데, 습하고 더운 날씨로 인해 팬케이크의 일부가 상했을 수도 있다. 각 팬케이크는 상했거나 상하지 않았거나 둘 중 하나의 상태이다.
- 맨 위에 있는 팬케이크는 $\cfrac{p}{q}$의 확률로 상했다.
- 바로 위에 상한 팬케이크가 있는 팬케이크는 $\cfrac{p}{q}$의 확률로 상했다.
- 바로 위에 상하지 않은 팬케이크가 있는 팬케이크는 $1-\cfrac{p}{q}$의 확률로 상했다.
상한 팬케이크가 상하지 않은 팬케이크보다 많을 확률을 구해보자.
입력
첫 번째 줄에 정수 $N$이 주어진다.
두 번째 줄에 두 정수 $p$, $q$가 주어진다.
출력
정답을 $\cfrac{a}{b}$ ($a$와 $b$는 서로소인 음이 아닌 정수)로 나타낼 때 $(a \times b^{-1}) \bmod 998\,244\,353$을 출력한다. $b^{-1}$은 $b$의 모듈러 곱셈에 대한 역원이다. 주어진 제약 조건 내에서 $(a \times b^{-1}) \bmod 998\,244\,353$의 값은 유일하게 존재함을 증명할 수 있다.
제한
- $1 \leq N \leq 10^6$; $N$은 홀수
- $0 \leq p \leq q \leq 10^6$
- $q \neq 0$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $N \leq 10$ |
| 2 | 20 | $N \leq 10^{3}$ |
| 3 | 75 | 추가 제약 조건 없음 |
예제 입력 1
1 1 1
예제 출력 1
1
구하는 확률은 $\cfrac{1}{1}$이므로 $(1 \times 1^{-1}) \bmod 998\,244\,353$의 값인 $1$을 출력한다.
예제 입력 2
3 2 3
예제 출력 2
702468249
구하는 확률은 $\cfrac{16}{27}$이므로 $(16 \times 27^{-1}) \bmod 998\,244\,353$의 값인 $702\,468\,249$를 출력한다.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호