0727 nCr table print

더 정확하게는 nCr table’s row print이다.

원래 문제

\(\dbinom{n}{0} \cdots \dbinom{n}{n}\)을 \(10^9\)로 나눈 나머지들을 모두 출력.

\( n < 1000 \) 이라는 조건이 있어서 그냥 파스칼의 삼각형을 모두 저장하는 식으로 금방 풀긴 했는데, discussion보고 또 머릿속에 번쩍.

점화식을 이용하면 된다. 위키에도 나와 있듯이, $${\binom {n}{k}}={\frac {n+1-k}{k}}{\binom {n}{k-1}}$$

뭐… 이제 더 나아지거나 그러지는 않겠지 남은 여생에 말이다. ㅎㅎㅎ