Calculate multinomial coefficient

Question

I want to calculate multinomial coefficient mod 1e9 + 7. It equals: n! / (k0! * k1! * k2 * ... * km!)

In my case m = 3, k0 + k1 + k2 = n, so it would be: n! / (k0! * k1! * k2!) My code for this:

....
long long k2 = n - k1 - k0;
long long dans = fact[n] % MOD;
long long tmp = fact[i] % MOD;
tmp = (tmp * fact[j]) % MOD;
tmp = (tpm * fact[k]) % MOD;
res = (fact[n] / tmp) % MOD; // mb mistake is here...
cout << res;

fact[i] - factorial of i mod 1e9+7 It does not work on big tests

Answer 1

I hope I'm not linkfarming here, but here is a process of work, to solve your problem :

1. Naive implementations will always suffer from overflow errors. You have to be ready to exploit certain mathematical properties of the polynomial coefficient to reach a robust solution. Dave Barber does that in his library, where the recursive property is used (example for 4 numbers - the recursion stops when all branches are replaced by zero)

   multi (a, b, c, d) = multi (a − 1, b, c, d) + multi (a, b − 1, c, d) + multi (a, b, c − 1, d) + multi (a, b, c, d − 1)
   

2. Based on the above, David Serrano Martínez shows how an implementation that provides overflow control can be divised. His code can be used as easily as

   unsigned long long result_2 = multinomial::multi<unsigned long long>({9, 8, 4});
   

3. A third alternative would be to use (or learn from) libraries that are dedicated to combinatorics, like SUBSET. This is a bit more difficult code to read through due to dependencies and length, but invokation is as easy as

   int factors[4] = {1, 2, 3, 4};
   Maths::Combinatorics::Arithmetic::multinomial(4, factors)