0

I am using C++ programming language. We are given 3 integers $x,y,z$ and I have to calculate :-

$(x +y +z)!/(x!*y!*z!) $ modulo $p$

where , $p=10^9+7$

Also , $0<=x,y,z<=10^5$

I tried many approaches but none of them worked. Fermat's theorem also does not work here :(

In C++,the maximum value an integer can have is 10^18.

Firex Firexo
  • 295
  • 1
    What are the values of $x,y,$ and $z$? – CardioidAss22 Jun 26 '19 at 16:21
  • 1
    @Cardioid_Ass_22 I've mentioned it. They can be anything between [0,10^5]...I want to know a way to calculate this in my C++ compiler :-) – Firex Firexo Jun 26 '19 at 16:22
  • Are you looking for an approach to simplify the calculation in general, rather than a specific answer? If so, please clarify in your question what size of value you can handle in your calculation. – CardioidAss22 Jun 26 '19 at 16:24
  • @Cardioid_Ass_22 Yes, you got it right :-) – Firex Firexo Jun 26 '19 at 16:25
  • Is this a Project Euler question? – Brian Tung Jun 26 '19 at 16:33
  • @BrianTung No.....but maybe similar to some of its questions.. – Firex Firexo Jun 26 '19 at 16:38
  • 2
    I don't think it's good idea to bloat MSE with programming challenges off the whole website. – metamorphy Jun 26 '19 at 16:40
  • All operations involved are binary operations: $+$, $\cdot$ and even the factorial is just a multiplication. So if you keep reducing all the operations modulo $p$ along your way, the worst case will be to multiply two number close to $10^9$ which should still be in the range of C++ representation of integer. – Zubzub Jun 26 '19 at 16:40
  • This is better suited to be a question on https://stackoverflow.com if you are even facing a problem to code or have an mvce. – Rahul Gohil Jun 26 '19 at 16:42
  • (Towards the answer: build tables of $n\mapsto(n!\bmod p)$ and $n\mapsto(n!^{-1}\bmod p)$ for $n\leqslant N:=3\cdot 10^5$. The first is built using $0!=1$ and successive multiplications $\bmod p$; the second is built downwards, using $N!^{-1}\bmod p$ computed from $N!\bmod p$ any way you like, and again successive multiplications $\bmod p$.) – metamorphy Jun 26 '19 at 16:45
  • @metamorphy I think it is problematic to calculate n!-inverse mod p .. – Firex Firexo Jun 26 '19 at 16:49
  • @metamorphy This is how I calculate n!mod p = (1%p2%p3%p4%p5%p*....n%p)......but the question is how do I calculate n^-1 ! mod p ?? – Firex Firexo Jun 26 '19 at 16:53
  • What is "problematic"? Extended Euclidean, or even just modular exponentiation (since $a\not\equiv 0\implies a^{-1}\equiv a^{p-2}\pmod{p}$). – metamorphy Jun 26 '19 at 16:53
  • Say, in our case, a=n! .... So I have to calculate (n!)^p-2 (mod p) .........Try to know that (x^y)%n can only be calculated when x<=10^9.....in our case, x=n!>>>>10^9 – Firex Firexo Jun 26 '19 at 16:56
  • You can use PARI C library. Let p=10^9+7;x=10^5-1;y=10^5-11;z=10^5-21;, check in pari/gp calculator Mod((x+y+z)!/(x!*y!*z!),p), output is Mod(912505566, 1000000007). – Dmitry Ezhov Jun 26 '19 at 17:46

1 Answers1

0

This question was asked by me and I have found the answer.

You basically want to calculate $ k!/a!*b!*c!$ mod $p$

which can be re-written as :- $(k!$ mod $p)$ * $(1/a!)$mod $ p$ * $(1/b!)$mod $p$ * $(1/c!)$ mod $p$

To calculate m!%p:-

int fact[Maxn];

fact[0] = 1;

for(int i = 1; i < Maxn; i++)

{

fact[i] = 1LL * fact[i - 1] * i % Mod;

}

To calculate (1/x!) mod p :-

int ifact[Maxn];

ifact[0] = 1;

for(int i = 1; i < Maxn; i++)

{

ifact[i] = 1LL * ifact[i - 1] * inverse(i, Mod) % Mod;

}

Firex Firexo
  • 295