Сполучення з повтореннями#11723

Сполучення з повтореннями (Розбір)

Ця задача зводиться до обчислення числа сполучень з повтореннями, що відповідає розв’язанню рівняння:

x_{1} + x_{2} + ... + x_{k} = n,

x_1 + x_2 + ...+ x_k = n,

де

$x_{i}$ x_i — кількість об'єктів, розміщених на $i$ -му місці,
$k$ — кількість місць.
$n$ — загальна кількість об'єктів.

Кожне $x_{i}$ x_i може бути будь-яким невід'ємним цілим числом. Кількість розв’язків цього рівняння визначається формулою (задача Еолімп $11551$ ): $C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1}.

Приклад

У першому прикладі ( $k = 3, n = 4$ k = 3, n = 4) відповідь дорівнює $C_{6}^{2} = (6 \cdot 5) /2 = 15$ C_6^2 = (6 \cdot 5) / 2 = 15.

У другому прикладі ( $k = 3, n = 2$ k = 3, n = 2) відповідь дорівнює $C_{4}^{2} = (4 \cdot 3) /2 = 6$ C_4^2 = (4 \cdot 3) / 2 = 6.

Реалізація алгоритму

Визначимо константи та масив $d p$ для запам'ятовування значень біноміального коефіцієнта.

#define MAX 201
#define MOD 1000000007
long long dp[MAX][MAX];

Функція Cnk обчислює значення біноміального коефіцієнта $C_{n}^{k}$ C_n^k за модулем $M O D = 1 0^{9} + 7$ MOD = 10^9 + 7.

long long Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % MOD;
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d", &k, &n);
memset(dp, -1, sizeof(dp));

Обчислюємо і виводимо відповідь $C_{n + k - 1}^{k - 1}$ C_{n + k - 1}^{k - 1}.

printf("%lld\n", Cnk(n + k - 1, k - 1));