+ 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!
+ 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!
+ 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~
+ '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.
+ 혹시라도 문제가 된다면 바로 조취를 취할테니, 말해주시면 감사하겠습니다!
+ 이번에도 많은 것을 배우게 해준 '이항계수3' 문제!
+ 해당 문제를 제대로 풀기 위해서는 배경 지식이 필요한데, 최소 '이항계수', '페르마의 소정리', '거듭제곱' 이렇게 3가지가 필요합니다.
+ 해당 문제를 풀기위해 간단히 정리하였으며, 보다 자세한 지식은 참고사이트를 확인해주세요~
[이항계수]
+ 이항계수란 n개의 원소에서 r개의 원소를 뽑아내는 경우의 수입니다.
+ 즉, 조합인 nCr을 구하는 것입니다.
+ nCr을 구하는 식은 n!/(r!(n-r)!) 입니다.
+ 이항계수와 관련된 법칙은 여러가지가 있지만, 가장 대표적으로 사용되는 법칙이 있습니다.
=> nCr = (n-1)Cr + (n-1)C(r-1)
+ 해당 법칙을 이용하지면, 작은 범위의 n에 한해서 문제를 풀 수 있습니다. 하.지.만. 11401문제를 풀기 위해서는 턱없이 부족합니다.
[페르마의 소정리]
+ 페르마의 소정리란, p가 소수이고 a가 정수일 때, 다음을 만족한다는 것입니다.
+ 위의 식의 뜻은, a^p를 p로 나눈 나머지가 a를 p로 나눈 나머지와 같다는 것입니다.
(a^p % p) = (a % p)
+ 여기서 끝이 아니라, 역수을 구해야 합니다. 역수이란, 특정 값 A에 대해서, A*X = 1이 나오게 하는 X를 말하는 것입니다.
+ 페르마의 소정리에서 양쪽에 a를 나눠주게되면
+ 위의 식을 발견하실 수 있으며, 양쪽에 a를 한 번 더 나눠 줌으로써, a의 역수가 a^(p-2) 임을 알게 되실 겁니다.
+ 이 식을 이항계수와 연관지으면, 아래의 식이 성립하게 됩니다.(문제의 %p를 대입)
nCr = n!/(r!(n-r)!) % p
-> A = n!, B = (r!(n-r)!)
-> (A*B^(-1)) % p
-> ((A % p)*(B^(-1) % p)) % p
-> B^(-1)은 B의 역수
-> (A*B^(p-2)) % p
+ 이로써, 분수가 아닌, 정수의 곱으로 이항계수를 표현할 수 있게 되었습니다.
+ 왜 정수로 표현해야하냐면, p로 나눠줘야 하는데, 분수는 나눠주기 힘들기 때문입니다.!
[거듭제곱]
+ p-2승 만급 거듭제곱을 해줘야 합니다.
+ 여러 방법이 있지만, 저는 2진수 표현법을 사용하였습니다.
+ 거듭제곱을 보면, A^2a = (A^a)^2 임을 알고 있으실 겁니다. 더 나아가, A^6a = (A^a)^6 = (A^a)^4 * (A^a)^2 = (A^a)^(2^2) * (A^a)^2 임을 알 수 있습니다.
+ 즉, 구하고자 하는 값을 2의 지수승의 합으로 나타낼 수 있습니다.
+ 그리고 이를 자세히보면, 지수를 2진법으로 나타낸 것과 같음을 발견할 수 있습니다.
a^14 = a^8 * a^4 * a^2
+ 이 것을 활용하여 거듭제곱을 구하게되면, O(logN)의 시간복잡도로 결과를 구할 수 있음을 알게 되실 겁니다!
*** 이해가 안되시면, 손으로 직접 적어가며 확인해보시면 됩니다~
*** 이해하는데 정말 시간 오래 걸렸다... 흑흑흑...
[코드]
+ 코드는 https://www.acmicpc.net/problem/11401의 문제풀이 과정을 참고하였습니다.
** 참고사이트 **
<문제관련>
- http://jason9319.tistory.com/169
- http://koosaga.com/entry/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98-nCr-mod-p-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0
<이항정리>
- https://namu.wiki/w/%EC%9D%B4%ED%95%AD%EC%A0%95%EB%A6%AC#rfn-3
- http://makefortune2.tistory.com/109
<페르마의 소정리>
- https://onsil-thegreenhouse.github.io/programming/problem/2018/04/02/problem_combination/
- http://weeklyps.com/entry/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98-%EC%86%8C%EC%A0%95%EB%A6%AC-%EC%9E%89%EC%97%AC%EC%97%AD%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0
- http://freshrimpsushi.tistory.com/121
<거듭제곱>
- http://return-true.tistory.com/1
Copyright © -강정이좋아- 무단 전재 및 재배포는 하지 말아주세요.
'요리 레시피 > Algorithm' 카테고리의 다른 글
| [자료구조] Union-Find, 유니온파인드 (0) | 2018.10.22 |
|---|---|
| [다익스트라] 다익스트라 - 유명한 최단거리 찾기 알고리즘!!! (0) | 2018.03.27 |
| [DFS][BFS] DFS 와 BFS (0) | 2018.03.27 |
| [Dp] DP에서 배열 사용 (0) | 2018.03.26 |
| [BackJoon] 충격의 N-Queen 문제 feat.9663번(N-Queen) (0) | 2018.03.26 |