2
$\begingroup$

for calculating the value of choosing r items from n items where q are of same kind, and we should take %m , i used the following relation

  • (nPr/q!) %m where m is prime

For calculating this

  • i calculated n!

  • n!%m

  • then, i calculated (n-r)! and multiplied it with q!, i.e temp = (n-r)!*q!;

  • Then i mulitplied modular mulitplicative inverse of temp with n! and took mod of result

    but am not getting the correct answer..E.g if n= 3 ; r = 2; q = 2 then the expected result is (3P2/2!)%1000000007 = 3 but am getting 250000004 ..I can't understand my mistake here..Thanks.

  • 0
    @DanAndrews: thanks..2012-06-04

1 Answers 1

4

The method you've described is correct, so there must be a bug in your implementation. In this case (n=3, r=2, q=2, m=1000000007):

n! = 6 temp = (n-r)!*q! = 2 Multiplicative inverse of 2 (mod m) = 500000004  result = (6*500000004) % 1000000007 = 3, the expected result. 
  • 0
    thanks interjay..indeed there was a mistake in my implementation..2012-06-04