retroin   2달 전

보통 nCk 를 손으로 계산하는 방식에서 착안했습니다.

즉, N, N-1, .., N-K+1 중에 K, K-1, ..., 1의 배수인 수를 찾아 나눈 다음, 최종적으로 남겨진 수들을 차례대로 곱해가는 것이죠. 

예시) 20C4 = (20*19*18*17)/(4*3*2*1) 을 구해야하는데, 20은 4의 배수이고 18은 3과 2의 배수이므로 5*19*3*17 을 계산합니다.

약분 완료된 분모를 이전 결과에 곱하고, overflow가 발생하지 않도록 10007로 나눈 나머지를 다음 결과로 대입했습니다.

(a * b) % d = ((a % d) * b) % d 인 것으로 알고 있는데, 왜 틀렸을까요?

num[i]는 1000이하이고, res는 10007 이하인데 overflow가 발생할 여지가 있을까요?

circlezer0   2달 전

틀렸습니다가 나오는거로 보아 overflow가 문제가 아니라 계산 결과가 그냥 틀린 것 같습니다.

circlezer0   2달 전

input : 1000 500

output : 6513

answer : 5418

댓글을 작성하려면 로그인해야 합니다.