이항계수3 파이썬

일단 페르마의 소정리를 알아야한다

https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-11401-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9D%B4%ED%95%AD-%EA%B3%84%EC%88%98-3-%EA%B3%A8%EB%93%9C1-%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5

[백준 11401 파이썬] 이항 계수 3 (골드1, 분할 정복)

여기 자세하게 설명되어있다

 a가 정수  P가 소수일때

a**p%p=a%p이다

p가 큰수로 실험해보았는데 같은 결과가 나오는것을 확인했다

원리가 뭘까?

https://m.blog.naver.com/a4gkyum/220768006509

페르마의 소정리 (내용과 증명)

이곳을 참고함

 

페르마의 소정리를 이용해 변환해준다

그렇게해서 만들어진 수식은 모두 관계가 곱셈으로 이루어져있어서

전체에 나머지 공식을 대입할수있게된다

 

첫번째 제출에서 너무깊은 재귀에 대한 에러가 발생했고

재귀가 발생하지않도록 반복문을 이용한 코드로 다시 작성을 하였다

그렇게 하니 이번엔 메모리 에러가 떳다

# 이항 계수3(11401번)
# 이항계수를 구하는 공식은 n!/k!(n-k)! 와같다~
N,K=map(int, input().split())
p=1000000007
d={}

def factorial_mod(number,p): # 팩토리얼의 나머지 구하는 공식
    try:
        return d[f'{number}_{p}_{number}f']
    except:
        d[f'{number}_{p}_1f']=1%p
        for i in range(2,number+1):
            d[f'{number}_{p}_{i}f']=(d[f'{number}_{p}_{i-1}f']*(i%p))%p
        return d[f'{number}_{p}_{number}f']       

def square_mod(num,ep,p): # 제곱의 나머지 구하는 공식
    try:
        return d[f'{ep}_{num}_{p}ep']
    
    except: 
        if ep>1:
            dived=ep//2
            d[f'{ep}_{num}_{p}ep']=(square_mod(num,dived,p) * square_mod(num,ep-dived,p)) % p
        else:
            d[f'{ep}_{num}_{p}ep']=num%p
        
        return d[f'{ep}_{num}_{p}ep']

print(((factorial_mod(N,p)) * (square_mod(factorial_mod(N-K,p),p-2,p)*square_mod(factorial_mod(K,p),p-2,p))%p)%p)

나의 접근 방식 자체에 문제가 있다고 판단하여 답지를 확인할 예정이다

답안을보니 어찌되었든 나랑 비슷하게 푼것을 확인했다

그래서 그냥 팩토리얼 나머지 구하는 부분에서 동적계획법 부분을 뺏다 그리고 제출했더니 맞았습니다 처리가 되었다