ps:problems:boj:11402
이항 계수 4
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 11402 |
| 문제명 | 이항 계수 4 |
| 레벨 | 플래티넘 5 |
| 분류 |
수학, 정수론 |
| 시간복잡도 | O(m + logn/logm) |
| 인풋사이즈 | n<=10^18, m<=2000 |
| 사용한 언어 | Python |
| 제출기록 | 28776KB / 64ms |
| 최고기록 | 56ms |
| 해결날짜 | 2021/01/20 |
풀이
- 모듈러스가 n보다 작은 소수일 경우의 이항 계수를 구하는 문제. 뤼카의 정리를 이용해서 푼다.
- 자세한 풀이는 이항 계수 - 모듈러스가 n보다 작은 소수일 때를 참고.
- 위의 링크에도 언급되어 있지만, C(n_i, k_i)를 계산하는 함수가, n_i < k_i 인 경우를 처리하는지 주의 할 것.
코드
from teflib import combinatorics
def main():
N, K, M = [int(x) for x in input().split()]
comb_table = combinatorics.CombTable(M - 1, M)
answer = 1
while N > 0:
N, n_mod = divmod(N, M)
K, k_mod = divmod(K, M)
answer *= comb_table.get(n_mod, k_mod)
print(answer % M)
if __name__ == '__main__':
main()- Dependency: teflib.combinatorics.CombTable
ps/problems/boj/11402.txt · 마지막으로 수정됨: 2021/01/31 17:18 저자 teferi
토론