백준 11402번 이항 계수 4 (Python 3)

 

Baekjoon online judge 11402번 파이썬

 

링크

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

11402번: 이항 계수 4

뤼카의 정리에 관한 문제.

메모이제이션으로 풀었다.

소스코드

import sys
from collections import deque
input=sys.stdin.readline


#뤼카정리



n,k,m=map(int,input().split())

dp=[[0 for _ in range(2010)] for _ in range(2010)]

for i in range(m):
    dp[i][0]=1
    for j in range(1,i+1):
        dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%m

ans=1

while n or k:
    ans*=dp[n%m][k%m]
    n//=m
    k//=m
    ans%=m
print(ans)