BJ11401 이항계수3

BJ11401 이항계수3

2020.02.09

자연수 N에서 K를 뽑는 경우의 수 % 1000000007

Solution1

• N 팩토리얼 / (K 팩토리얼*(N-K)팩토리얼)
• 이렇게 나눠주는 경우는 분자,분모를 구하는 과정에서 팩토리얼 곱셈 도중 나머지를 계산하는 방식을 사용할 수가 없다.
• 즉, 분자와 분모가 long long의 범위를 넘어가게 된다.

Solution2>

• nCr = n-1Cr-1 + n-1Cr 임을 이용한다.
• 이렇게 하면 합으로 문제가 바뀌기 때문에 합을 1000000007로 매번 나누어 줄 수 있다. (즉, 범위를 넘기지 않을 수 있다.)
• 그렇지만 이렇게 하면 호출의 횟수가 급격히 늘어나게 된다. (마치 피보나치 수열처럼)
• N의 범위가 4000000 이하이므로 시간초과가 난다.
• DP를 사용해서 메모이제이션을 한다고 하더라도 O(N^2)이 되어 시간초과를 피할 수 없다.
• 또 메모이제이션을 하게 되면 400만 X 400만 의 공간이 필요하게 되어 메모리를 많이 사용하게 된다.

Solution3>

• 페르마의 소정리 를 이용한다.