ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1734. Endgame Database

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