nCr mod m

vamsi_ism 2014-12-16 10:29:41 UTC #1

What are the best ways to calculate nCr (n choose r) mod m where m is a large prime and n, r are smaller than m?

vamsi_ism 2014-12-16 14:38:37 UTC #2

I was referring to this problem: http://www.spoj.com/problems/RIVALS/
I got AC with pre-calculation of factorial values with PyPy but still TLE with Pyth 2.7
Any ideas?

leppyr64 2014-12-16 15:56:23 UTC #3

google.com/#q=fast+n+choose+modulo