nCr com Fatoriais Pré-calculados

Muitos problemas perguntam de quantas maneiras é possível escolher r itens de n, escrito como nCr. As competições pedem essa contagem sob um módulo primo. 🧮

A fórmula clássica é nCr igual a n fatorial dividido por r fatorial vezes n menos r fatorial. O problema é que a divisão sob um módulo não é direta.

Um único fatorial cresce astronomicamente, portanto calcule cada um módulo p. Isso mantém todos os valores pequenos, enquanto a fórmula continua exata sob o módulo.

Construa uma matriz de fatoriais uma única vez, até o maior n de que você precisa. Cada entrada é a anterior multiplicada pelo índice, calculada módulo p à medida que você avança.

A fórmula divide por dois fatoriais, portanto você precisa dos inversos modulares deles. Lembre-se: o inverso transforma a divisão em uma multiplicação simples.

Calcule o inverso do maior fatorial apenas uma vez usando Fermat, com pow e o expoente p menos 2. Essa única chamada inicia o restante do processo.

Obtenha os outros inversos de fatoriais em uma única passagem para trás, cada um a partir do próximo multiplicado pelo índice. Não são necessárias chamadas adicionais a pow.

Agora, nCr é simplesmente fact[n] multiplicado por inv_fact[r] e por inv_fact[n menos r], tudo módulo p. São três consultas e duas multiplicações por consulta.

Depois do pré-cálculo, cada resposta de combinação é obtida em O(1). É por isso que esse padrão é excelente quando um problema pede milhares de valores de nCr.

Se r for negativo ou maior que n, a resposta será 0. Verifique esse limite primeiro para nunca acessar uma posição fora das suas matrizes de fatoriais.

Defina o tamanho da matriz como o maior n entre todas as consultas, mais uma pequena margem. Um limite pequeno demais é uma causa comum de erros de índice aqui.

Depois do pré-cálculo, qual é a velocidade de uma consulta nCr?

Você pré-calcula os fatoriais e seus inversos uma vez e, depois, responde a cada nCr em O(1) com três consultas. Verifique os limites de r e dimensione as matrizes com tamanho suficiente. 🏆