Binomial əmsallar 1#318

Binomial əmsallar 1 (Həll təhlili)

Hesablama $64$ mərtəbəli işarəsiz uzun tam ədədlərdən (unsigned long long) istifadə ediləcək. Aydındır ki,

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}

Dəyişən $r es$ -ə $1$ dəyərini verək, sonra $i$ -dən $1$ -ə qədər $k$ üçün $r es$ -i $\frac{n - i + 1}{i}$ {n - i + 1 \over i} ilə artıracağıq. Hər dəfə $i$ ilə bölünmə tam şəkildə olacaq, lakin çoxalma zamanı daşıma baş verə bilər. Qoy $d = U ¨ O D (r es, i)$ d = ÜOD(res, i). Bu hal

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

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

ondan

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

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

ilə yenidən yazırıq.

Bu üsulda çoxalmanın artıq daşıması baş verməyəcək (cavab $64$ mərtəbəli işarəsiz uzun tam ədəddir). Əvvəlcə $(n - i + 1) / (i / d)$ (n - i + 1 ) / (i / d) bölünməsini, sonra $r es / d$ çoxalmaları tamamlanmalıdır.

$C_{n}^{k}$ C_n^k hesablamaq üçün $k$ iterasiya edəcək. Bəs $C_{2000000000}^{1999999999}$ C_{2000000000}^{1999999999} hesablamalısınızsa nə etməli? Cavab $2^{64}$ 2^{64} ilə məhdudlaşmayacaq, buna görə belə giriş məlumatı mümkündür. $C_{n}^{k} = C_{n}^{n - k}$ C_n^k = C_n^{n-k} olduğundan, $n - k < k$ n-k < k olduqda $k = n - k$ k = n-k qoymaq lazımdır.

Misal

Nu aşağıdakı misalı nəzərdən keçirə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}

Qoy $r es = 15$ res = 15, və çoxalma $r es \cdot \frac{4}{3} = 15 * \frac{4}{3}$ res \cdot {4 \over 3} = 15 * {4 \over 3} başa qalıb. Hesablayırıq $d = U ¨ O D (15, 3) = 3$ d = ÜOD(15, 3) = 3. Buna görə $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.

Alqoritmin icrası

gcd funksiyası $a$ və $b$ ədədlərinin ən böyük ortaq bölənini hesablayır.

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

Cnk funksiyası binomial əmsalın $C_{n}^{k}$ C_n^k dəyərini hesablayır.

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++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

C++

Java tətbiqi

Jaвa-da işarəsiz növlər yoxdur, buna görə BigInteger sinifindən istifadə etmək lazımdır.

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 tətbiqi - comb

Binomial əmsalı hesablamaq üçün $co mb (n, k) = C_{n}^{k}$ comb(n, k) = C_n^k funksiyasından istifadə edəcəyik.

import math

Tests $t$ sayını oxuyuruq.

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

Hazırda testin giriş məlumatlarını oxuyuruq.

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

Cavabı hesablayırıq və göstəririk.

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

Python tətbiqi

Cnk funksiyası binomial əmsalın $C_{n}^{k}$ C_n^k dəyərini hesablayır.

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

Proqramın əsas hissəsi. Tests $t$ sayını oxuyuruq.

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

Giriş məlumatlarını oxuyuruq.

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

Cavabı hesablayırıq və göstəririk.

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