$\binom{n}{k}$ módulo de la primera potencia para grandes $n$ y pequeños $k$

Question

Tengo que calcular varios valores de $\binom{n}{k}$ mod $p^a$ para prime $p$ en una gama de $k$ donde $n$ es grande y fija, y $k$ es pequeño y dinámico.

¿Hay alguna forma de acelerar el proceso? Si utilizo identidades iterativas, a menudo me encuentro con problemas de coprimalidad que me impiden invertir los denominadores.

He encontrado el método de Granville (Lucas generalizado) pero es demasiado lento para calcularlo para cada binomio.

Límites: $n$ en torno a $10^8$ más o menos. $k$ como máximo en torno a $10^5$ . El módulo puede ser una potencia prima hasta $10^8$ (aproximadamente).

Answer 1

Pruebe a utilizar $\binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1}$ . Para evitar problemas con la división por $k$ en caso de que $k$ tiene un exponente de $p$ sólo hay que tener en cuenta el exponente de $p$ por separado. Por ejemplo tener un rastreador acumulativo llamado pow . Ahora bien, si $p \mid n$ sustituya $n$ con $n/p$ en el numerador, e incrementar pow por 1. Del mismo modo, si $p \mid k$ sustituya $k$ con $k/p$ en el denominador y disminuir pow por 1. Al final, multiplica lo que tienes por $p^\text{pow}$ . Un poco de pseudocódigo:

function binommod(n, k, p, a): [Returns an array of nCi mod p^a for i ranging from 0 to k]
    answers = an array of k+1 integers.
    currentans = 1
    pow = 0
    answers[0] = 1
    for i in [1, k]:
        numer = n - i + 1
        denom = i
        while p | numer:
            numer = numer / p
            pow = pow + 1
        while p | denom:
            denom = denom / p
            pow = pow - 1
        currentans = currentans * numer / denom (mod p^a) [You should have an algorithm for this already, provided p does not divide k]
        answers[i] = currentans * p^pow (mod p^a)
    return answers