티스토리 뷰
https://www.acmicpc.net/problem/11402
11402번: 이항 계수 4
첫째 줄에 \(N\), \(K\)와 \(M\)이 주어진다. (1 ≤ \(N\) ≤ 1018, 0 ≤ \(K\) ≤ \(N\), 2 ≤ \(M\) ≤ 2,000, M은 소수)
www.acmicpc.net
Lucas 정리라는 것을 새롭게 알게 된 문제입니다.
Lucas 정리는 nCr % p (p : 소수) 를 쉽게 구할 수 있는 방법입니다.
일반적으로 공식을 이용하거나 ( nCr = n! / ((n-r)! * r!) ) dp 등을 이용해 풀 수 있습니다. (nCr = n-1Cr-1 + n-1Cr 이용한 dp)
Lucas 정리는 mCn % p 를 다음과 같이 나타낼 수 있습니다.
여기서 m_i, n_i 는 다음과 같습니다.
증명은 위키피디아에도 간략히 나와있으므로 참고하시면 됩니다. https://ko.wikipedia.org/wiki/%EB%A4%BC%EC%B9%B4%EC%9D%98_%EC%A0%95%EB%A6%AC
뤼카의 정리 - 위키백과, 우리 모두의 백과사전
뤼카의 정리(Lucas' theorem, -定理)는 수론과 조합론에서 이용되는 정리로, 프랑스인 수학자 에두아르 뤼카(Édouard Lucas)의 이름이 붙어 있다. 이 정리는 어떤 조합의 수를 소수 p에 대해 법 p 상에서
ko.wikipedia.org
(m_i, n_i) 에 해당하는 값을 구할 때만 dp를 이용해 구하였고, p 진법 polynomial 형태로 계산하면 계수가 m_i < n_i 인 경우가 발생할 수 있습니다. 이 경우는 (m_i, n_i) = 0 으로 처리합니다.
코드는 다음과 같습니다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1765 닭싸움 팀 정하기 C++ (0) | 2022.02.07 |
|---|---|
| 백준 16562 친구비 c++ (0) | 2022.02.07 |
| 백준 2150 Strongly Connected Component C++ (0) | 2022.01.09 |
| 백준 9576 책 나눠주기 C++ (0) | 2021.12.20 |
| 백준 1202 보석 도둑 C++ (0) | 2021.12.10 |