Біноміальні коефіцієнти 1#318

Біноміальні коефіцієнти 1 (Розбір)

Обчислення будемо проводити з використанням $64$ -розрядних беззнакових цілих чисел (unsigned long long). Очевидно, що

C_{n}^{k} = \frac{n !}{k ! \cdot ( n - k )!} = \frac{n \cdot ( n - 1 ) \cdot ( n - 2 ) \cdot ... \cdot ( n - k + 1 )}{1 \cdot 2 \cdot 3 \cdot ... \cdot k} = \frac{n}{1} \cdot \frac{n - 1}{2} \cdot \frac{n - 2}{3} \cdot ... \cdot \frac{n - k + 1}{k}

C_n^k = {n! \over k! \cdot (n - k)!} = {n \cdot (n - 1) \cdot (n - 2) \cdot ... \cdot (n - k + 1) \over 1 \cdot 2 \cdot 3 \cdot ... \cdot k} = {n \over 1} \cdot {n - 1 \over 2} \cdot {n - 2 \over 3} \cdot ... \cdot {n - k + 1 \over k}

Присвоїмо змінній $r es$ значення $1$ , після чого будемо її множити на $\frac{n - i + 1}{i}$ {n - i + 1 \over i} для всіх $i$ від $1$ до $k$ . Кожного разу ділення на $i$ буде цілочисельним, однак при множенні можна отримати переповнення. Нехай $d = НОД (r es, i)$ d = НОД(res, i). Тоді операцію

r es = r es * (n - i + 1) / i

res = res * (n - i + 1 ) / i

перепишемо через

r es = (r es / d) * ((n - i + 1) / (i / d))

res = (res / d) * ((n - i + 1 ) / (i / d))

При такій реалізації переповнення при множенні не відбудеться (відповідь є $64$ -розрядним беззнаковим цілим числом). Зауважимо, що спочатку слід виконати ділення $(n - i + 1) / (i / d)$ (n - i + 1 ) / (i / d), а потім множення $r es / d$ на отримане частка.

Для обчислення $C_{n}^{k}$ C_n^k слід виконати $k$ ітерацій. Але що робити, якщо слід обчислити $C_{2000000000}^{1999999999}$ C_{2000000000}^{1999999999}? Відповідь не перевищить $2^{64}$ 2^{64}, тому такі вхідні дані можливі. Оскільки $C_{n}^{k} = C_{n}^{n - k}$ C_n^k = C_n^{n - k}, то при $n - k < k$ n - k < k слід покласти $k = n - k$ k = n - k.

Приклад

Розглянемо наступний приклад:

C_{6}^{3} = \frac{6}{1} \cdot \frac{5}{2} \cdot \frac{4}{3} = 15 \cdot \frac{4}{3}

C_6^3 = {6 \over 1} \cdot {5 \over 2} \cdot {4 \over 3} = 15 \cdot {4 \over 3}

Нехай $r es = 15$ res = 15, і залишилося виконати множення $r es \cdot \frac{4}{3} = 15 * \frac{4}{3}$ res \cdot {4 \over 3} = 15 * {4 \over 3}. Обчислимо $d = НОД (15, 3) = 3$ d = НОД(15, 3) = 3. Тому $15 \cdot \frac{4}{3} = (15/3) \cdot \frac{4}{3/3} = 5 \cdot \frac{4}{1} = 20$ 15 \cdot {4 \over 3} = (15 / 3) \cdot {4 \over 3 / 3} = 5 \cdot {4 \over 1} = 20.

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

Функція gcd обчислює найбільший спільний дільник чисел $a$ і $b$ .

unsigned long long gcd(unsigned long long a, unsigned long long b)
{
  return (!b) ? a : gcd(b,a % b);
}

Функція Cnk обчислює значення біноміального коефіцієнта $C_{n}^{k}$ C_n^k.

unsigned long long Cnk(unsigned long long n, unsigned long long k)
{
  unsigned long long CnkRes = 1, t, i;
  if (k > n - k) k = n - k;
  for(i = 1; i <= k; i++)
  {
    t = gcd(CnkRes, i);
    CnkRes = (CnkRes / t) * ((n - i + 1) / (i / t));
  }
  return CnkRes;
}

C++

Основна частина програми. Читаємо вхідні дані. Послідовно обробляємо тести.

scanf("%d",&t);
while(t--)
{
  scanf("%llu %llu",&n,&k);
  res = Cnk(n,k);
  printf("%llu\n",res);
}

C++

Java реалізація

У Java відсутні unsigned типи, тому слід скористатися класом BigInteger.

import java.util.*;
import java.math.*;

public class Main
{
  static BigInteger Cnk(BigInteger n, BigInteger k)
  {
    BigInteger ONE = BigInteger.ONE, CnkRes = ONE;
    if (k.compareTo(n.subtract(k)) > 0) k = n.subtract(k);
    for(BigInteger i = ONE; i.compareTo(k) <= 0; i = i.add(ONE))
      CnkRes = CnkRes.multiply(n.subtract(i).add(ONE)).divide(i);
    return CnkRes;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int tests = con.nextInt();
    while(tests-- > 0)
    {
      BigInteger n = con.nextBigInteger();
      BigInteger k = con.nextBigInteger();
      BigInteger res = Cnk(n,k);
      System.out.println(res);
    }
  }
}

Java

Python реалізація – comb

Для обчислення біноміального коефіцієнта скористаємося вбудованою функцією $co mb (n, k) = C_{n}^{k}$ comb(n, k) = C_n^k.

import math

Читаємо кількість тестів $t$ .

t = int(input())
for _ in range(t):

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

  n, k = map(int, input().split())

Обчислюємо і виводимо відповідь.

  res = math.comb(n, k)
  print(res)

Python реалізація

Функція Cnk обчислює значення біноміального коефіцієнта $C_{n}^{k}$ C_n^k.

def Cnk(n, k):
  res = 1
  if k > n - k: k = n – k
  for i in range(1, k + 1):
    res = res * (n - i + 1) // i
  return res

Основна частина програми. Читаємо кількість тестів $t$ .

t = int(input())
for _ in range(t):

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

  n, k = map(int, input().split())

Обчислюємо і виводимо відповідь.

  res = Cnk(n, k)
  print(res)