1
$\begingroup$

How to calculate the value of below expression where $M$ is 1000000007 (prime) and $N$ can be any large number $\le 1000$?

\[\frac{N!}{(N/2)!(N/2)!} \mathbin{\%} M\]

It is possible to simplify it like \[\frac{(N/2 + 1)(N/2 + 2)\cdots N}{(N/2)!}\] but then $(N/2)!$ is still a huge number to calculate.

Now can also simply it further like (n/2 + 1)*(n/2 + 2)...*(n-1)/3*4...(n/2-1). But this still isn't enough.

Is it possible to break it down further?

$\endgroup$
3
  • $\begingroup$ Your question is ambiguous. The simplest way to calculate factorial is the way you stated above. This is obviously from an algorithm problem that tackles the overflow of the factorial function. But to attract good responses to your question, you need to explain what you want exactly. $\endgroup$ – user31280 Feb 6 '13 at 20:44
  • $\begingroup$ this is actually in reference to quesion stackoverflow.com/questions/14736514/… and this is an algorithm problem. $\endgroup$ – g4ur4v Feb 6 '13 at 20:47
  • 1
    $\begingroup$ could you include the reference in your question? $\endgroup$ – user31280 Feb 6 '13 at 20:54
2
$\begingroup$

What is needed here is Modular Multiplicative Inverse i.e. $x$ i sthe multiplicative inverse of a iff $$ax \equiv aa^{-1} \equiv 1 \mod m$$ The multiplicative inverse of $a$ modulo $m$ exists if and only if $a$ and $m$ are coprime, so if $m$ is prime then every number that is not a multiple of $m$ has a multiplicative inverse modulo $m$.

To solve the problem $ax \equiv 1 \mod m \implies ax-mk=1| k\in \mathbb Z$, since our problem satisfies Bézout's Identity ($a$ and $m$ are coprime.) one can apply Extended Euclidean Algorithm. You can find the algorithm in Python code here.

To compute $\cfrac {n!}{a!\times b!}$ modulo $m$, you can rewrite this as $n!\times(a!)^{-1}\times(b!)^{-1}$. As long as none of $a,\ b,\ $or $n$ is greater $m$, then there shouldn't be a problem at all.

$\endgroup$
1
  • 1
    $\begingroup$ And if any of $a,b,n$ are greater than $m$, Lucas's theorem applies since $m$ is prime. $\endgroup$ – Erick Wong Feb 7 '13 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.