Algoritmos: ¿Cómo calculo (nCr)% p donde n <= 10 ^ 18 yr <= 10 ^ 5 en C ++?

Answer 1

Suponiendo que p es primo, utilizaremos el teorema de Lucas para calcular [matemáticas] \ binom {n} {r} \ hspace {0.2cm} (mod \ hspace {0.05cm} p) [/ math]. Según el teorema de Lucas: –

[matemáticas] \ binom {n} {r} = \ prod_ {i = 1} ^ {k} \ binom {n_i} {r_i} \ hspace {0.2cm} (mod \ hspace {0.05cm} p) [/ math ]

dónde

[matemáticas] n = n_kp ^ k + n_ {k-1} p ^ {k-1} + ………… + n_1p ^ 1 + n_0 [/ matemáticas]

y

[matemáticas] r = r_kp ^ k + r_ {k-1} p ^ {k-1} + ………… + r_1p ^ 1 + r_0 [/ matemáticas]

son las expansiones de base de n y r respectivamente.

Esto usa la convención que [math] \ binom {n} {r} = 0 if n <r [/ math].

En cuanto a la implementación, puede echar un vistazo al siguiente método codificado en C ++: –

#define LL largo largo
vector Hecho;
vector Invfact;
vector Inv;

// Factorial de preprocesamiento y sus inversas en el tiempo O (p).
cálculo vacío (int P)
{
Hecho claro ();
Invfact.clear ();
Hecho tamaño (P);
Invfact.resize (P);
Inv.clear ();
Inv.resize (P);

Hecho [0] = Hecho [1] = 1;
Invfact [0] = Invfact [1] = 1;
Inv [0] = 1;
Inv [1] = 1;

para (int i = 2; i <P; i ++)
{
Hecho [i] = (Hecho [i-1] * i)% P;
Inv [i] = ((PP / i) * Inv [P% i])% P;
}
}

// Calcula el módulo P de C (N, R) en tiempo O (log (n)).
LL Lucas (LL N, LL R, int P)
{
si (R N)
{
devuelve 0;
}

si (R == 0 || R == N)
{
retorno 1;
}

si (N> = P)
{
retorno (Lucas (N / P, R / P, P) * Lucas (N% P, R% P, P))% P;
}

return (Hecho [N] * (Invfact [NR] * Invfact [R])% P)% P;
}

Complejidad del algoritmo (incluido el preprocesamiento): – [matemáticas] O (p + \ log {} n) [/ matemáticas]

Answer 2

Utilizo las siguientes funciones para encontrar (nCr)%p :

plantilla
T MODPow (T base, T exp, T módulo)
{
% base = módulo;
T resultado = 1;
while (exp> 0) {
if (exp & 1) result = (result * base)% módulo;
base = (base * base)% módulo;
exp >> = 1;
}
resultado de retorno;
}
plantilla
T MOD Inverso (T a, T p)
{
return MODPow (a, p – 2, p);
}
plantilla
T MODBinomial (T n, T k, T p)
{
T numerador = 1;
para (T i = 0; i numerador = (numerador * (n – i))% p;
Denominador T = 1;
para (T i = 1; i <= k; ++ i)
denominador = (denominador * i)% p;
return (numerador * MODInverse (denominador, p))% p;
}

Para (nCr)%p = MODBinomial(n, k, p);

Answer 3

Debe dejar de hacer preguntas de la competencia en curso de CodeChef.

Ya ha preguntado cómo resolver el mismo problema STROPR en Algoritmos: ¿Cuál es el mejor algoritmo para calcular la suma de prefijos de una matriz para N veces?