22.07.14. 풀었던 문제들

백준 단계별 21 분할 정복

11401 이항계수 3 - 페르마의 소정리 쉣...

 

페르마 그는 신인가? 풀이는 아래와 같다.

 

이항계수 $_{n}C_{k} = \tfrac{n!}{(n-K)! \cdot k!} = \tfrac{n \cdot (n-1)\cdots (n-k+1)}{k \cdot (k-1) \cdots 1}$이다.

 편의를 위해 $A = n \cdot (n-1) \cdots (n-k+1), B = k \cdot (k-1) \cdots 1$라고 두자.

 한편, 페르마의 소정리에 의해 나누는 값 1,000,000,007(p라고 두자)은 소수이므로 $a^{p-1} \equiv 1 \% p$이다.

 그러면 이항계수를 $\tfrac{A}{B} \% p  = (AB^{-1}) \% p = (AB^{-1} \times 1) \% p$로 둘 수 있는데,

 $(AB^{-1} \times B^{p-1}) \% p = (AB^{-1} \% p \times B^{p-1} \% p) \% p = ((AB^{-1} \% p) \times 1) \% p = (AB^{-1}) \% p$이다. 

 따라서 이항계수 $(AB^{-1} \times 1) \% p가 (AB^{-1} \times B^{p-1}) \% p = (AB^{p-2}) \% p$로 바뀌게 된다.

 최종적으로 $(AB^{p-2}) \% p =  ((n \cdot (n-1) \cdots (n-k+1)) \times (k!)^{p-2} ) \% p$가 되고, 이는 O(log(p) + n)이 된다.

 

 

6549 Largest Rectangle in a Histogram

 

이분탐색 풀까

코포는 주말에