흙금이네 블로그

아이디어 모듈러 연산의 분배법칙과 페르마의 소정리로 계산식을 바꾼 후, 이분 탐색을 이용해 계산한다. 풀이 \(\binom{N}{K}\)는 \(\frac{N!}{K!(N-K)!}\)이고, \(\frac{N!}{K!(N-K)!}=\frac{N\cdot(N-1)\cdot\cdots\cdot(N-K+1)}{K!}\)이다. 결과값은 1,000,000,007로 나눈 나머지이므로 계산 과정에서 모듈러 연산의 곱셈에 대한 분배법칙을 이용할 수 있다. \((a\bmod p)\cdot(b\bmod p)=ab\bmod p\) 따라서 계산 과정에서 발생하는 중간값들을 모두 1,000,000,007로 나눈 나머지로 두고 계산할 수 있다. 모듈러 연산의 곱셈에 대한 분배법칙으로 분모와 분자를 각각 1,000,000,007로 나..