Estoy trabajando en un problema de programación donde tengo que calcular "n elegir k'. Estoy usando la relación de la fórmula
$$
{n\elegir k} = {n\elegir k-1} \frac{n-k+1}{k}
$$
así que no tengo que calcular enorme factoriales. Hay alguna forma de utilizar esta fórmula y realizar un seguimiento de los últimos 6 dígitos. Podría usted calcular el siguiente k, con sólo conocer algunos de los últimos dígitos.
Entiendo que esto es mucho pedir, así que todo lo que pedimos es un punto en la dirección correcta.
Las matemáticas son, por mucho, no es mi fuerte el tema.
Gracias de antemano.
Respuestas
¿Demasiados anuncios?
Robert Christie
Puntos
7323
Justin Walgran
Puntos
552
En términos de factoriales, probablemente no.
El % de repetición ${n \choose k} = {n \choose k-1} + {n-1 \choose k-1}$y solo mod $10^6$.
Alternativamente puede trabajar mod $2^6$y mod $5^6$ y combinar los dos resultados usando el Teorema chino del resto. Parece haber patrones interesantes en el mod de coeficientes binómicos prime poderes pero no sé si hay realmente fórmulas. Esto es probablemente más problemas que merece la pena, sin embargo.
Owen
Puntos
5680
Recuerdo que la resolución de SPOJ CANICAS que en realidad es la búsqueda de $\binom{n}{k}$,hay restricciones son también similares a este problema en la mano.
El pasado mes de enero este mismo problema (con mucho más difícil restricciones) las características Codechef de enero del cookfoff.Usted puede comprobar la editorial en la que explica el algoritmo, junto con la aplicación.
También puede que quiera usar $\binom{n}{k}=\binom{n}{n-k}$ a reducir el caso de que $k>n/2$.
El uso de $\binom{n}{k} = \binom{n}{k-1} \frac{n-k+1}{k}$ mod de un millón tiene un problema al $(k,10)\not=1$. Tal $k$ son divisores de cero mod de un millón, por lo que no se puede dividir por $k$ mod de un millón y obtener un resultado significativo.
Sin embargo, usted puede contar el número de factores de $p$ que están en $\binom{n}{k}$ primer $p$. Deje $s_p(n)$ ser la suma de la base $p$ dígitos de $n$. Entonces, el número de factores de $p$$\binom{n}{k}$$(s_p(k)+s_p(n-k)-s_p(n))/(p-1)$. Así, en lugar de multiplicar por $n-k+1$ y dividiendo por $k$, se multiplica por $n-k+1$ con todos los factores de $2$ $5$ eliminado y dividir por $k$ con todos los factores de $2$ $5$ eliminado. Al final, se multiplica por el número de factores de $2$ $5$ calculado anteriormente.
Por ejemplo, vamos a calcular $\binom{97}{89}=\binom{97}{8}$.
Aquí están $97$, $8$, y $89$ base $2$$5$, seguido por la suma de dígitos: $$ 97=1100001_2(3)=342_5(9) $$ $$ 8=1000_2(1)=13_5(4) $$ $$ 89=1011001_2(4)=324_5(9) $$ Por lo tanto, el número de factores de $2$$\binom{97}{89}$$(1+4-3)/(2-1)=2$, y el número de factores de $5$$(4+9-9)/(5-1)=1$. Por lo tanto, mod de un millón,
$$ \begin{align} \binom{97}{8} &=\frac{97}{1}\frac{96/32}{2/2}\frac{95/5}{3}\frac{94/2}{4/4}\frac{93}{5/5}\frac{92/4}{6/2}\frac{91}{7}\frac{90/10}{8/8}\times2^2\times5^1\\ &=\frac{97}{1}\frac{3}{1}\frac{19}{3}\frac{47}{1}\frac{93}{1}\frac{23}{3}\frac{91}{7}\frac{9}{1}\times4\times5\\ &=010441\times20\\ &=208820 \end{align} $$ Todo es bueno arriba ya que podemos dividir por $3$ $7$ mod de un millón.
Advertencia: Recuerde que modular la división es muy distinta a la estándar de la división de números enteros, racionales y reales. Se requiere la solución de una ecuación de Diophantine que generalmente implica el algoritmo de Euclides. Por ejemplo, $1/7=3\pmod{10}$ porque $3\times7=1\pmod{10}$.
