[python/백준] 11401번 : 이항 계수 3

 

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

 

 

⭐ 문제

 

n​Ck​ 값을 1000000007로 나눈 나머지를 구하는 문제

 

 

 

 

⭐ 코드 분석

 

1.  n​Ck​ = N! / (N-K)!K!

 

2. 나눗셈에 대해서는 분배 법칙이 성립하지 않으므로 곱셈에 대한 분배법칙 활용

 

3.이를 위해 페르마의 소정리 이용

 

---

페르마의 소정리

p가 소수, a가 정수일 때

ap≡a(modp)

세 줄 등호는 합동을 의미한다. (p로 나눈 나머지가 서로 같다)

이 식의 양 변을 a^2로 나눠주면

ap−2≡a1​(mod p) (a =/ 0)

 

---

 

 

 

4. 조합 공식을 곱셈 형태로  변형

 

 

 

 

5. 구현

 

1. 팩토리얼은 1 부터 N 까지 for문을 돌면서 %p 연산을 해주고 N! % p 를 리턴하는 함수 정의
2. 분자와 분모를 하나의 값 , top, bot 변수에 구해 놓자
3. 분할 정복 거듭 제곱 함수 정의 후  bot^(p-2)를 %p 연산 적용된 값으로 구할 때 사용
4.  top과 (bot^(p-2) % p)(여기서 거듭제곱 함수 활용) 를 곱하고 한번 더 %p를 해주면 결과 값

 

 

 

 

 

 

 

 

⭐ 코드

 

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
p = 1000000007

# 팩토리얼 값 계산(나머지 연산 적용)
def factorial(N):
    n = 1
    for i in range(2, N+1):
        n = (n * i) % p
    return n

# 거듭제곱 계산(나머지 연산 적용)
def square(n, k):
    if k == 0:
        return 1
    elif k == 1:
        return n
    
    tmp = square(n, k//2)
    if k % 2:
        return tmp * tmp * n % p
    else:
        return tmp * tmp % p

top = factorial(N)
bot = factorial(N-K) * factorial(K) % p

# 페르마의 소정리 이용해서 조합 공식 곱셈 형태로 변형
print(top * square(bot, p-2) % p)