문제

코드

def divCon(a,b):
    if b==1:
        return a%p
    else:
        div = divCon(a,b//2)

        if b%2==0: #짝수 
            return div*div%p
        else : #홀수 
            return div*div*a%p

n,k = map(int,input().split())
p = 1000000007

fact = [1 for _ in range(n+1)]
#factorial 계산 
for i in range(2,n+1):
    fact[i]=fact[i-1]*i%p

A = fact[n]
B = fact[n-k]*fact[k]%p 

print((A%p)*(divCon(B,p-2)%p)%p)

해설

크으... 단순히 문제만 보고 덤볐다가 엄청 후두려 맞은 문제이다...
그냥~~ 그냥 ~ 팩토리얼 계산하면 나는 될줄알았지~~₩
그런데 나머지 연산자 법칙도 알아야하고 ~ 페르마의 소정리도 알아야하고~거듭제곱분할정복하는 방법도 알아야하는~ 아주 종합세트적인 문제였다!!!

그래도 이 문제를 풀면서 많은 것을 얻어갔다!
역시 쉬운난이도 100문제보다 이런 문제 1개가 더 알찬거같다.
그럼 ! 해설을 시작하겠는데 시작하겠다!

이 문제를 해결하기 위해서는 총4가지의 개념을 알아야 된다고 생각한다.

첫번째 : 페르마의 소정리

두번째 : 나머지 연산자의 법칙

세번째 : 컴비네이션을 팩토리얼로 분해하고 팩토리얼 구하기

네번째 : 분할정복을 통한 거듭제곱 계산하기

우선, 첫번째 부터 하나씩 정리해서 코드를 작성해보자.

첫번째 : 페르마의 소정리

페르마의 소정리 처음들으면 되게 생소하고 신기하다..
이 알고리즘을 간단히 말하자면
p가 소수이고, a가 p의배수가 아닌 정수일때, 다음 조건을 만족한다.

이를 머리속에 일단 넣어두자 !

두번째 : 나머지 연산자의 법칙

이는 앞선 포스터에서 잘 정리해뒀다!
그 포스트를 보면 알수있는 사실이 바로 !
분수를 계산할때는 나머지 연산자가 제대로 작용하지 않으므로 페르마의 소정리를 활용해야한다는 것이다.

세번째 : 컴비네이션을 팩토리얼로 분해하고 팩토리얼 구하기

nCk를 다르게 분수로 표현하고 첫번째, 두번째 개념을 적용하면

자 ! 어떤가 !! 컴비네이션에 p를 나눈나머지를 이렇게 표현할 수있다!!
신기하지 않은가

그렇기에 이걸 계산하기 위해서 B의 p-2승은 네번째 개념을 사용하면
더 빠른 속도로 계산이 가능할 것이다.

네번째 : 분할정복을 통한 거듭제곱 계산하기

def divCon(a,b):
    if b==1:
        return a%p
    else:
        div = divCon(a,b//2)

    if b%2==0: #짝수 
        return div*div%p
    else : #홀수 
        return div*div*a%p

이는 앞선 포스트에서 소개한 함수이기에 설명을 덧붙이지 않겠다.

그런데.. 팩토리얼 계산을 

fact = [1 for _ in range(n+1)]
#factorial 계산
for i in range(2,n+1):
fact[i]=fact[i-1]*i%p

이와 같은 방식으로 하지 않고 math에서 팩토리얼 함수를 가져와서 쓰면 시간초과가 떴다..
이에 대한 이유는 차차알아보겠다..
못찾았다..
이렇게 리스트에 저장하는게 시간이 더 빠른갑..?
쳇 제기랄... 
풀어도 뭔가 시원하지 않다..! 
그리고 나머지연산자는 차아아아암 신경쓸게 많은거같다..! 
곳곳에 해줘야하니.. 복잡행....