[백준] 11050 - 이항계수2

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

11051번: 이항 계수 2

• 조합의 출력을 10,007로 나누어야 하는 문제이다.
• 계산과정에서 나온 값들은 dpArray 혹은 dpDictionrary에 저장하는 식으로 진행하면된다.
• 값들은 모두 10007 나머지 값들을 사용하면 간단히 구할 수 있다.

# 25, 12 -> 5200300
N, M = map(int, str(input()).split())
dpDict = dict();
dpDict[0] = 1
dpDict[1] = 1

# r!
rFact = 1
if M % 10007 in dpDict.keys(): rFact = dpDict.get(M % 10007)
else : 
    for r in range(1, (M%10007)+1): rFact *= r
    dpDict[M % 10007] = rFact

# n-r!
nrFact = 1
if (N-M) % 10007 in dpDict.keys(): nrFact = dpDict.get((N-M) % 10007)
else:
    for nr in range(1, (N-M) % 10007 + 1): nrFact *= nr
    dpDict[(N-M) % 10007] = nrFact

# n!
nFact = 1
if N % 10007 in dpDict.keys(): nFact = dpDict.get(N % 10007)
else:
    for n in range(1, N % 10007 +1): nFact *= n
    dpDict[n%10007] = nFact

print(int(nFact // (rFact*nrFact)) % 10007)