모듈로 곱셈 역원 (1) 썸네일형 리스트형 [백준 11401][C++] 이항 계수 3 문제 https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 과정 이 문제는 중요 포인트가 두 가지 있었다. (1) 분할 정복으로 연산 시간 감소 POW연산을 수행할 때 지수가 최대 4000000까지 입력이 가능하다. 따라서 일반적인 연산으로는 시간 초과가 발생한다. 이를 두배로 적용시켜 분할 정복하는 power 함수를 만들어 해결한다. 2^22 = 4194304의 값을 가진다. 하나씩 곱셈하는 식으로 power 연산을 구현하면 최대 4000000번 수행해야 하는 연산.. 이전 1 다음
