I have been exploring the idea of computing Binomial Coefficients $$$\binom{n}{k}\mod m$$$ where $$$n$$$,$$$k$$$ and $$$m$$$ are all 64 bit integers.ie $$$m$$$ is any integer rather than being a prime. I have found few solutions here where they first factorise and then proceed for each $$$p_i^k$$$.
- Express as $$$(\binom{n}{k}\mod p_1^{e_1})\mod p_2^{e_2})$$$ ... $$$\mod p_t^{e_t})$$$
- then strip off all the factors of pi from n!, k! and (n-k)!
- and compute netexpo = total exponents of $$$p_i$$$ on numerator — total exponents of $$$p_i$$$ on on denominator
- and then $$$ n! * ModularInverse((n — k)!) * ModularInverse(k!) * (p_1)^{netexpo}$$$
- details of this method for each $$$(\binom{n}{k}\mod p_1^{e_1})$$$ have been discussed on math.stackexchange (at least for cases when each $$$p_i$$$ is 32 bit integer.
However almost none of them scale for large 64 bit $$$m$$$. Just changing the data type wont fix as it overshoots memory. There can be two parts to the problem
- m is 64-bit but all of its prime factors are 32-bit
- m is 64-bit and one of its prime factor is 64-bit
None of the solutions submitted on yosupo implements either. My understanding is if they are implementing the algorithm similar to the discussion on math.stackexchange just scaling up datatype should scale for the first part (ie m is 64-bit but all of its prime factors are 32-bit). But I found even in those cases it overshoots memory.
Any suggestions on how we can modify the code to scale to 64 bit for each of $$$n,k,m$$$ ? I should call it out upfront that I have already gone through https://mirror.codeforces.com/blog/entry/65178 and https://mirror.codeforces.com/blog/entry/12878 .
