combinatoria de $\binom{10^9} {r}$ mientras que $1 \leq r \leq10^9 \pmod {10^6+3}$

Question

Cómo calcular $ \binom{n}{r} \mod m$ cuando $1\leq n,\: r\leq 10^9$ y $m=10^6+3$ . He intentado haciendo Tamiz de inverso factorial y multiplicativo $10^6+3 \mod m$ . ¿hay alguna solución en $\mathcal{O}(m)$ ?

Answer 1

$10^6+3$ es un número primo

Utilizando Teorema de Lucas :

$$\binom{n}{r} = \Pi_{i=0}^{k} \binom{n_i}{r_i}\ mod\ p$$

donde $n,r$ se expresan en base $p$ expansión.

$n=n_0 + n_1p + n_2p^2 + .. + n_kp^k$

$r=r_0 + r_1p + r_2p^2 + .. + r_kp^k $

Los coeficientes se encuentran en $O(log_k(n))$ y el número de $mod$ están limitadas por $O(k)$ mientras $\binom{n_i}{r_i}$ puede determinarse en $O(1)$ probablemente usando una tabla de búsqueda.