How to modulo this formula?

Question

I would like to write this formula in C++ language:

$$\tiny{element_{k} (n-1)!(\frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{4}) }$$ (2<=n<=1e5), (1<=k<=n), (2<=M<=1e9) M is modulo. How to mathematically work around programming language constraints? Since in C++ a number has a range of 2^128. Unfortunately in this formula there are a lot of cases which effectively make modulation difficult. Example: ((n-k)!) mod M can be equal to 0, or ((n-1)(n-2))/4 may not be an integer in C++. I will be very grateful for any help.

Answer 1

the constraints you put looklike they come from either competitive programming (which I assume) or a university course, usually it's enough to precompute some tables/arrays, one way of doing this is like this

if M is a large prime (i.e. $M > n$ and M is prime) then we can simply precompute the factorials as

factorial[0] = 1
for i = 1:n
     factorial[i] = (factorial[i - 1] * i)%M

this way you have $k!$ for all $k$, $\frac{1}{k!}$ can be obtained in two ways, either as $k!^{M - 2}$ where I used fermat's little theoreom, this works in O(log(M)), or you can precompute it in similar way, this works also if M is composite but all prime factors of M are $> n$, in that case you should replace $M - 2$ in the exponent with $\phi(M) - 1$ where $\phi(n)$ is euler's totient function, then evaluating any expression can be done in O(1) or O(log(M)) depending on your implementation (e.g. $\frac{a!}{b!} = {factorial(a)}*{factorial(b)}^{\phi(M) - 1}$)

when M has at least one factor $\leq n$ then you need to be careful, there are several ways to proceed from here but the simpliest is

1. factor M to $\prod p_i^{e_i}$
2. compute the answer mod $p_i^{e_i}$ for each $i$ then combine the answers using chinese remainder theorem (CRT)

computing the answer modulu $p_i^{e_i}$ should be similar to the original case but take care of when the result is zero.

note that in any of the calculations the largest number that can appear is $(M - 1)^2$ which happens when you multiply $M - 1$ by itself, and after taking mod all numbers are mapped to $[0, M)$ (aka $\mathbb{Z_M}$ or $\mathbb{Z}/M\mathbb{Z}$)