Thursday, December 11, 2014

Czech, Polish and Slovak Preparation Camp 2007 - Triangulations


put m = n-2 and T(n) = D(m).

D(0) = D(1) = 1.

D(m) = D(0)D(m-1) + D(1)D(m-2) + ... + D(m-1)D(0) = ( 2m C m ) / (m+1)

D(m)/D(m-1) = 2(2m-1)/(m+1)

Using Fenwick Tree, we can update each prime numbers' multiplication(with exponentiation by squaring)

Total Time Complexity equals O(N log N).

My Source Code(hongjun7 소스 코드)

No comments:

Post a Comment