Лемурині вечірки - базова#11269

Лемурині вечірки - базова (Розбір)

На $n$ місць деякі види будуть представлені двома лемурами, а деякі одним. Нехай вибрано $i$ пар лемурів (тобто $i$ видів представлені двома особами). Зробити такий вибір можна $C_{k}^{i}$ C_k^i способами. Після цього у VIP зоні залишиться $n - 2 i$ n - 2i вільних місць. Ці місця можна зайняти лемурами з $k - i$ k - i залишкових видів, вибираючи по одному лемуру з кожного. Кількість способів вибрати таких лемурів обчислюється за формулою $C_{k - i}^{n - 2 i}$ C_{k - i}^{n - 2i}.

Так як значення $i$ може приймати будь-яке ціле значення від $0$ до $k$ , отримуємо підсумкову відповідь як суму по всім можливим $i$ :

i = 0 \sum k C_{k}^{i} \cdot C_{k - i}^{n - 2 i}

\sum_{i = 0}^k C_k^i \cdot C_{k - i}^{n - 2i}

Приклад

Розглянемо другий приклад, в якому є $k = 4$ k = 4 пари лемурів і $n = 3$ n = 3 місця у VIP-зоні. За формулою отримуємо:

i = 0 \sum k C_{4}^{i} \cdot C_{4 - i}^{3 - 2 i} = C_{4}^{0} \cdot C_{4}^{3} + C_{4}^{1} \cdot C_{3}^{1} = 4 + 12 = 16

\sum_{i = 0}^k C_4^i \cdot C_{4 - i}^{3 - 2i} = C_4^0 \cdot C_4^3 + C_4^1 \cdot C_3^1 = 4 + 12 = 16

Випишемо тільки ненульові доданки. Значення $C_{n}^{k}$ C_n^k будемо вважати рівним нулю, якщо виконується одна з трьох нерівностей: $k < 0$ k < 0, $n < 0$ n < 0 або $k > n$ k > n.

Позначимо лемурів літерами ${a, a, b, b, c, c, d, d}$ \{a, a, b, b, c, c, d, d\}, де однакові літери відповідають лемурам одного виду.

Доданку $C_{4}^{0} \cdot C_{4}^{3} = 4$ C_4^0 \cdot C_4^3 = 4 відповідає ситуація, коли жодна пара лемурів одного виду не обрана, тобто кожен з трьох вибраних лемурів належить до різних видів. Можливі чотири вибірки такі:

Розглянемо доданок $C_{4}^{1} \cdot C_{3}^{1} = 12$ C_4^1 \cdot C_3^1 = 12. У цьому випадку з одного виду обираються два лемура (існує $4$ варіанти такого вибору). На залишкове одне місце вибирається один лемур з трьох залишкових видів. Таким чином, всього можливо $12$ різних варіантів:

Очевидно, що розмістити на $3$ місцях по два лемура з двох різних видів неможливо. Тому всі інші доданки суми дорівнюють нулю.

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

Оголосимо константи.

#define MAX 1000001
#define MOD 1000000007

Оголосимо масиви:

$f a c t$ містить факторіали чисел за модулем $M O D$ ;
$f a c t in v$ factinv містить значення, обернені факторіалам чисел за модулем $M O D$ :

fact[n] = n! mod 1000000007
factinv[n] = n! -1 mod 1000000007

typedef long long ll;
ll fact[MAX], factinv[MAX];

Функція pow обчислює ступінь числа за модулем: $x^{n} m o d p$ x^n~mod~p.

ll pow(ll x, ll n, ll p)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
  return (x * pow(x, n - 1, p)) % p;
}

Функція inverse знаходить число, обернене $x$ за простим модулем $p$ . Оскільки $p$ — просте число, за малою теоремою Ферма виконується рівність:

x^{p - 1} m o d p = 1 для всякого 1 \leq x < p

x^{p-1}~mod~p~=~1~для~всякого~1 \le x < p

Це рівність можна переписати у вигляді:

(x \cdot x^{p - 2}) m o d p = 1,

(x \cdot x^{p-2})~mod~p~=~1,

звідки випливає, що оберненим до $x$ є число $x^{p - 2} m o d p$ x^{p-2}~mod~p.

ll inverse(ll x, ll p)
{
  return pow(x, p - 2, p);
}

Функція Cnk обчислює значення біноміального коефіцієнта за наступною формулою:

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}

C_n^k = \frac{n!}{k! (n - k)!}

ll Cnk(int n, int k)
{
  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}

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

scanf("%d %d", &k, &n);

Заповнюємо масиви факторіалів $f a c t$ і $f a c t in v$ factinv.

fact[0] = 1;
for (i = 1; i < MAX; i++)
  fact[i] = (fact[i - 1] * i) % MOD;

factinv[0] = 1;
for (i = 1; i < MAX; i++)
   factinv[i] = inverse(fact[i], MOD);

C++

Обчислюємо відповідь за формулою $\sum_{i = 0}^{k} C_{k}^{i} \cdot C_{k - i}^{n - 2 i}$ \sum_{i = 0}^k C_k^i \cdot C_{k - i}^{n - 2i}. Значення біноміального коефіцієнта $C_{n}^{k}$ C_n^k вважаємо рівним нулю, якщо виконується одна з трьох умов: $k < 0$ k < 0, $n < 0$ n < 0 або $k > n$ k > n.

res = 0;
for (i = 0; i <= k; i++)
{
  if (n - 2 * i < 0 || k - i < 0 || n - 2 * i > k - i) continue;
  res = (res + Cnk(k, i) * Cnk(k - i, n - 2 * i)) % MOD;
}

Друкуємо відповідь.

printf("%lld\n", res);