Discussion @ 1734. Endgame Database @ Timus Online Judge

Need optimization

Posted by bsu.mmf.team 2 Nov 2009 22:44

Can anybody tell me how to calucate bynomial coefficients with a help of the fastest method?

Re: Need optimization

Posted by PersonalJesus 2 Nov 2009 23:20

What about C(n,k) = n!/k!*(n-k)! ,where '!' denotes factorial.

Re: Need optimization

Posted by MSDN 3 Nov 2009 12:58

fastest method С[n][k]=C[n-1][k]+C[n-1][k-1]

Re: Need optimization

Posted by svr 3 Nov 2009 13:13

also:
C(n,k)=(C(n,k-1)*(n-k+1)*Inv(k,p))%p because 100000007 is
prime

PS. And this method helped to Ac.

Edited by author 03.11.2009 15:23

Re: Need optimization

Posted by MSDN 3 Nov 2009 17:16

Oh!
Thanks! It's cool formula :)

Re: Need optimization

Posted by bsu.mmf.team 22 Jan 2010 01:41

Edited by author 29.06.2011 22:31

Discussion of Problem 1734. Endgame Database