[BOJ][Python] 백준 19124번 - Binomial Coefficient
문제 링크: https://www.acmicpc.net/problem/19124문제 풀이정수론 설명은 정말 간단한 문제. ${}_{n}C_{k} \bmod 2^{32}$를 구하면 된다.$2^{32}$는 매우 큰 수이기도 하고, 합성수여서 뤼카 정리를 사용하기에도 빡세보인다. 먼저 가장 쉬운 판별을 해보자.${}_{n}C_{k} = 2^E \cdot U$로 나타낼 때 $E \geq 32$이면 나누어떨어지므로 $U$를 계산할 필요가 없어진다. 이 $E$를 구하는 방법이라면 Legendre's formula를 이용해도 좋고 어렵지 않다. 다만 $p = 2$의 경우에는 $\nu_{2}(n!) = n - s_2(n)$($n$을 이진수로 나타내었을 때 $1$의 개수)로도 나타낼 수 있으니, $\nu_{2}({}_{..
BOJ
2025. 6. 25. 13:07
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 그리디
- 볼록 껍질
- MST
- DP
- greedy
- 다이나믹 프로그래밍
- Python
- 너비 우선 탐색
- convex hull
- BOJ
- Topological Sorting
- 브루트포스
- 수학
- Sorting
- BFS
- backtracking
- math
- 파이썬
- Implementation
- 집합과 맵
- 최소 신장 트리
- Simulation
- 백트래킹
- set
- TEXT
- 정렬
- 시뮬레이션
- Brute Force
- 위상 정렬
- 구현
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 |
글 보관함