Combinatória em Programação

Aula por Caique Paiva

Conhecimento prévio necessário:

Combinatória Básica em Matemática
Exponenciação Rápida

Alguns problemas bem comuns em programação envolvem contar quantidade de algumas coisas. Existem algumas maneiras de fazer isso, como com programação dinâmica, ou então, calcular uma fórmula explícita. Para isso, normalmente nós precisamos saber usar algumas funções, como fatorial ou binomiais, então, precisamos saber como calcular essas funções. Não vamos entrar nas provas do teoremas nessas aulas, mas todas elas podem ser encontradas aqui.

Definições

Primeiramente, defina $n! = 1 \times 2 \times 3 \times \cdots \times n$ (Chamamos de $n$ fatorial), indutivamente, definimos $0! = 1$ . Nós sabemos que esse número é a quantidade de permutações de um conjunto de $n$ elementos. Além disso, seja $n \choose k$ para ser

${n \choose k} = \frac{n!}{k! (n-k)!}$

(Lê-se $n$ escolhe $k$ ). Sabemos que esse número representa a quantidade de maneiras de escolher $k$ elementos num conjunto de $n$ elementos.

Como calcular?

Primeiro, vamos olhar pros fatoriais. Veja que $20!$ já é absurdamente grande e já passa do limite de inteiro, por isso, é normal os problemas pedirem para calcular as respostas módulo algum primo grande. Vamos chamar esse primo de $p$ . Então, queremos calcular $n!$ módulo $p$ , e conseguimos fazer isso em $O(N)$ ! Basta ver que $n ! = n \times (n-1) !$ , então, podemos montar uma recorrência! Veja o código para entender melhor a recorrência:

Veja que colocamos um vetor para salvar as respostas dos fatoriais. Isso é importante, pois nos problemas podemos chamar essa função várias vezes, e então, para não recalcular coisas, salvamos os números nesse vetor.

Agora, como vamos fazer para calcular binomiais? Pelo mesmo motivo dos fatoriais, é como os problemas pedirem para calcular as respostas módulo algum primo grande. Seja esse primo $p$ . Então, temos duas maneiras de calcular:

Forma Analítica

Sabemos que

${n \choose k} = \frac{n!}{k!(n-k)!} \pmod {p}$

Então, podemos calcular esse valor em $O(N + \log p)$ , pois, sabemos colo calcular $n!, k!$ e $(n-k)!$ , então, só precisamos calcular $(k!)^{-1}$ e $((n-k)!)^{-1}$ módulo $p$ , mas podemos calcular isso usando o pequeno teorema de fermat (Prova desse teorema aqui). Para calcular $a^{-1}$ módulo $p$ , basta ver que, se $p \not \mid a$ então

$a^{p-1} \equiv 1 \pmod {p}$

$\Longrightarrow a^{p-2} \equiv a^{-1} \pmod {p}$

Então, precisamos calcular $a^{p-2}$ módulo $p$ , que com exponenciação rápida, podemos calcular em $O(\log p)$ . Veja o código para entender melhor:

Forma Rercussiva

Sabemos pelo lema de Stifel que

${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$

Então, podemos montar uma dp para resolver essa recorrência! Vamos definir um vetor ch[ $N$ ][ $N$ ], os casos bases vão ser $ch[n][0] = 1$ e $ch[0][n] = 0$ para todo $n > 0$ , e $ch[0][0] = 1$ . Então, a transição vai ser

$ch[n][k] = ch[n-1][k] + ch[n-1][k-1]$

Veja o código para saber mais

Esse código roda em $O(N^2)$ , porém, ele é bem mais fácil de codar, então quando o $N$ do problema for pequeno, vale a pena fazer esse método.

Recomendo você tentar codar essas funções por conta própria. Para submeter, use esse problema.

Exemplo

Dada uma string, sua tarefa é calcular o número de strings diferenets que podem ser criadas usando seus caracteres

Input

O único input é uma string de tamanho $n$ . Todos os caracteres estão entre a-z.

Output

Imprima o número de strings diferentes módulo $10^9 +7$ .

Exemplo

Entrada	Saída
aabac	20

Entrada	Saída
abcdef	720

Solução

Vamos chamar de $a_i$ a quantidade de letras $i -$ 'a' que tem na string. Por exemplo, no primeiro exemplo, $a_0 = 3, a_1 = 1, a_2 = 1, a_3 = 0 \cdots, a_25 = 0$ . Então, vamos calcular a resposta. Primeiro, vamos escolher as posições para colocar os caracteres $a$ , então, temos $n \choose a_0$ possibilidades. Agora, para colocar os caracteres $b$ , temos $n - a_0 \choose a_1$ possibilidades, pois não podemos colocar $a, b$ na mesma posição, e assim vai.

Em geral, a quantidade de maneiras que temos de colocar o caractere $i-$ 'a' é $n - a_0 - \cdots - a_{i-1} \choose a_i$ , e então, a resposta vai ser a multiplicação de todas essas respostas.

Veja o código para ficar mais claro

[collapse]

Problemas Propostos

Os problemas estão em ordem de dificuldade, mas a partir do Hits Different, os problemas ficam bem mais difíceis.