É possível perceber que tipos diferentes de especialidades não influenciam uns aos outros na contagem de soluções. Portanto, podemos considerar a distribuição de um tipo de cada vez para todas as pessoas. Isso nos leva a uma programação dinâmica (dp), onde definimos dp[i][j] como o número de formas de distribuir as primeiras i tipos de especialidades de modo que j pessoas tenham recebido pelo menos uma especialidade.
Na transição, consideramos quantas pessoas adicionais receberão a especialidade atual. Primeiro, damos uma unidade a cada uma dessas pessoas, e então distribuímos as restantes entre as j pessoas que já possuem especialidades. Como especialidades do mesmo tipo são idênticas, duas distribuições são consideradas diferentes apenas se pelo menos uma pessoa receber uma quantidade diferente. Isso é equivalente a encontrar o número de soluções inteiras não-negativas da equação x₁ + x₂ + ... + xj = k, o qual pode ser resuelto diretamente usando o método das barras (插板法). Formalmente, sendo a[i] a quantidade de unidades do tipo i de especialidade:
[dp_{i, j} = \sum\limits_{k = 0} ^ {\min(a_i, j)} \dbinom{m - j + k}{k} \times \dbinom{a_i - k + j - 1}{j - 1} dp_{i - 1, j - k} ]
O resultado final é dp[m][n].
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1005;
const int MOD = 1000000007;
int pessoas, tipos;
int quantidade[MAX];
int dinamica[MAX][MAX];
int binomial[MAX * 2][MAX * 2];
int lerInteiro() {
int valor = 0, sinal = 1;
char caractere = getchar();
while (caractere > '9' || caractere < '0') {
if (caractere == '-') sinal = -1;
caractere = getchar();
}
while (caractere >= '0' && caractere <= '9') {
valor = valor * 10 + caractere - '0';
caractere = getchar();
}
return valor * sinal;
}
int adicionar(int x, int y) {
int resultado = x + y;
if (resultado >= MOD) resultado -= MOD;
return resultado;
}
int multiplicar(int x, int y) {
return (1LL * x * y) % MOD;
}
int main() {
pessoas = lerInteiro();
tipos = lerInteiro();
for (int i = 1; i <= tipos; i++) {
quantidade[i] = lerInteiro();
}
// Construir tabela de coeficientes binomiais
for (int i = 0; i < MAX * 2; i++) {
binomial[i][0] = 1;
}
for (int i = 1; i < MAX * 2; i++) {
for (int j = 1; j <= i; j++) {
binomial[i][j] = adicionar(binomial[i-1][j-1], binomial[i-1][j]);
}
}
dinamica[0][0] = 1;
random_shuffle(quantidade + 1, quantidade + tipos + 1);
// Programação dinâmica O(n³)
for (int i = 1; i <= tipos; i++) {
for (int j = 1; j <= pessoas; j++) {
for (int k = 0; k <= min(j, quantidade[i]); k++) {
int termo = multiplicar(
multiplicar(
binomial[pessoas - j + k][k],
binomial[quantidade[i] - k + j - 1][j - 1]
),
dinamica[i - 1][j - k]
);
dinamica[i][j] = adicionar(dinamica[i][j], termo);
}
}
}
printf("%d", dinamica[tipos][pessoas]);
return 0;
}
No entanto, esta abordagem de programação dinâmica possui complexidade O(n³), o que não é suficiente para resolver o problema dentro dos limites de tempo. Pode-se notar que este processo de dp na verdade garante progressivamente que cada pessoa tenha pelo menos uma especialidade para escolher. Essencialmente, estamos contando as distribuições onde exatamente n pessoas possuem especialidades.
Para esse tipo de problema de "exatamente", podemos considerar usar a inversão binomial (também conhecida como princípio da inclusão-exclusão). Porém, surge uma questão: definir que i�hojas possuem especialidades na verdade nos leva de volta ao problema original. A estratégia geral é considerar o problema inverso: contar quantas pessoas NÃO recebem nenhuma especialidade, pois essa condição é mais simples de garantir.
Definimos então f[i] como o número de maneiras de garantir que exatamente i pessoas NÃO recebam nenhuma especialidade:
[f_i = \dbinom{n}{i} \prod\limits_{j = 1} ^ m \dbinom{a_i + n - i - 1}{n - i - 1} ]
Seja g[i] o número de maneiras em que exatamente i pessoas NÃO recebem especialidades. Podemos derivar a relação entre f e g:
[f_i = \sum\limits_{j = i} ^ n \dbinom{j}{i} g_j ]
Portanto:
[g_0 = \sum\limits_{i = 0} ^ n (-1) ^ i \dbinom{n}{i} \prod\limits_{j = 1} ^ m \dbinom{a_i + n - i - 1}{n - i - 1} ]
O cálculo direto desta fórmula nos dá a resposta desejada.
#include <bits/stdc++.h>
using namespace std;
const int LIMITE = 2005;
const int MOD = 1000000007;
int pessoas, tipos;
int resposta, temporario;
int quantidade[LIMITE];
int coeficiente[LIMITE][LIMITE];
int lerInteiro() {
int valor = 0, sinal = 1;
char caractere = getchar();
while (caractere > '9' || caractere < '0') {
if (caractere == '-') sinal = -1;
caractere = getchar();
}
while (caractere >= '0' && caractere <= '9') {
valor = valor * 10 + caractere - '0';
caractere = getchar();
}
return valor * sinal;
}
int adicionar(int x, int y) {
int resultado = x + y;
if (resultado >= MOD) resultado -= MOD;
return resultado;
}
int subtrair(int x, int y) {
int resultado = x - y;
if (resultado < 0) resultado += MOD;
return resultado;
}
int multiplicar(int x, int y) {
return (1LL * x * y) % MOD;
}
int main() {
pessoas = lerInteiro();
tipos = lerInteiro();
for (int i = 1; i <= tipos; i++) {
quantidade[i] = lerInteiro();
}
// Pre-calcular coeficientes binomiais
for (int i = 0; i < LIMITE; i++) {
coeficiente[i][0] = 1;
}
for (int i = 1; i < LIMITE; i++) {
for (int j = 1; j <= i; j++) {
coeficiente[i][j] = adicionar(coeficiente[i-1][j-1], coeficiente[i-1][j]);
}
}
// Aplicar inversão binomial
for (int i = 0; i <= pessoas; i++) {
temporario = 1;
for (int j = 1; j <= tipos; j++) {
temporario = multiplicar(
temporario,
coeficiente[quantidade[j] + pessoas - i - 1][pessoas - i - 1]
);
}
int termo = multiplicar(temporario, coeficiente[pessoas][i]);
if (i & 1) {
resposta = subtrair(resposta, termo);
} else {
resposta = adicionar(resposta, termo);
}
}
printf("%d", resposta);
return 0;
}