Mmedv2 il öncə

Binomial əmsalı

Seçim $n$ elementdən $k$ elementin seçilməsidir, burada verilmiş $n$ elementdən $k$ elementi seçilir. Bu halda, elementlərin sıralanması fərqli olan dəstlər (lakin tərkibi fərqli olmayan) eyni hesab olunur. Seçimlərin bu xüsusiyyətinə görə onlar yerləşdirmələrdən fərqlənirlər.

Məsələn, $5$ elementdən ibarət olan çoxluğu nəzərdən keçirək: ${1, 2, 3, 4, 5}$ \{1, 2, 3, 4, 5\}. ${2, 1, 3}$ \{2, 1, 3\} və ${3, 2, 1}$ \{3, 2, 1\} dəstləri seçim olaraq eyni hesab olunur (yerdəyişmə olaraq fərqli olsalar da), çünki eyni elementlərdən ${1, 2, 3}$ \{1, 2, 3\} ibarətdir.

$n$ -dən $k$ -yə qədər seçimlərin sayının hesablanması üçün formula belədir

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

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

$C_{n}^{k}$ C_n^{k} ədədləri binomial əmsallar adlanır.

$n$ elementdən ibarət olan çoxluqdan sıfır element seçdiyimiz zaman əslində "boş" seçim edirik. Bu kontekstdə boş çoxluq düzgün seçim hesab olunur. Təsəvvür edin ki, $n$ topları olan bir qutunuz var və onlardan $0$ ədədini seçmək istəyirsiniz. Heç bir şey seçməsəniz belə, bu yenə də düzgün seçim variantıdır. Beləliklə, $C_{n}^{0}$ C_n^{0} $n$ -dən $0$ element seçmənin sayını bildirir ki, bu da $1$ -ə bərabərdir.

Bunu heç bir element seçməmək üçün yalnız bir yol kimi nəzərə ala bilərik ki, bu da nəticədə $1$ verir.

C_{n}^{0} = \frac{n !}{0 ! \cdot ( n - 0 )!} = \frac{n !}{1 ! \cdot n !} = 1

C_n^{0} = {n! \over 0! \cdot (n - 0)!} = {n! \over 1! \cdot n!} = 1

$n$ elementdən ibarət olan çoxluqdan bir element seçdiyimiz zaman $n$ seçmə variantımız var: $n$ elementdən istənilən birini seçə bilərik. Məsələn, $1$ -dən $5$ -ə qədər ədədlərdən ibarət olan çoxluqdan ( ${1, 2, 3, 4, 5}$ \{1, 2, 3, 4, 5\}) bir ədəd seçsək, bu çoxluqdan bir ədəd seçmək üçün $5$ variantımız var.

$C_{n}^{1}$ C_n^{1}-in dəyəri $n$ -ə bərabərdir, çünki $n$ elementdən ibarət olan çoxluqdan bir elementi seçmənin $n$ yolu var.

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

C_n^{1} = {n! \over 1! \cdot (n - 1)!} = n

$n$ elementdən ibarət olan çoxluqdan $2$ element seçdiyimiz zaman cütlüklər təşkil edirik. Belə bir cütlüyün qurulması üçün əvvəlcə bir elementi, sonra isə ikinci elementi seçirik.

Birinci elementi $n$ elementdən seçə bilərik.
Birinci elementi seçdikdən sonra ikinci elementi seçmək üçün $n -1$ element qalır (çünki eyni elementi təkrarən seçə bilmərik).

Beləliklə, $n$ elementdən ibarət olan çoxluqdan cüt elementlərin seçilmə üsullarının ümumi sayı birinci və ikinci elementləri seçmənin yollarının hasilinə bərabərdir: $n \cdot (n -1)$ n \cdot (n – 1).

Lakin, hər bir cütlük iki dəfə sayılır, çünki cütlükdə elementlərin sırası əhəmiyyət daşımır. Məsələn, $(p, q)$ və $(q, p)$ eyni cütlük hesab olunur. Bunu nəzərə alaraq, cütlüklərin ümumi sayını $2$ -yə bölmək lazımdır. Beləliklə, $C_{n}^{2}$ C_n^{2} $n \cdot (n -1) /2$ n \cdot (n – 1) / 2-yə bərabərdir.

C_{n}^{2} = \frac{n !}{2 ! \cdot ( n - 2 )!} = \frac{n \cdot ( n - 1 )}{2}

C_n^{2} = {n! \over 2! \cdot (n - 2)!} = {n \cdot (n - 1) \over 2}

Simmetriya xüsusiyyəti: $C_{n}^{k} = C_{n}^{n - k}$ C_n^{k} = C_n^{n - k}.

$n$ elementdən $k$ elementi seçmənin sayı $n$ elementdən $(n - k)$ elementi seçmənin sayına bərabərdir. Amma $n$ elementdən $(n - k)$ elementi seçmənin $C_{n}^{n - k}$ C_n^{n - k} yolu var. Deməli, $C_{n}^{k} = C_{n}^{n - k}$ C_n^{k} = C_n^{n - k}.

Tapşırıq. Aşağıdakı binomial əmsalların qiymətlərini hesablayın:

1) $C_{5}^{2}$ C_5^{2}	3) $C_{5}^{4}$ C_5^{4}	5) $C_{8}^{1}$ C_8^{1}
2) $C_{8}^{3}$ C_8^{3}	4) $C_{7}^{5}$ C_7^{5}	6) $C_{8}^{5}$ C_8^{5}

Yığma formulu: $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$ C_n^{k} = C_{n-1}^{k-1} + C_{n-1}^{k}.

İspat. Bərabərliyin sağ tərəfindəki dəyəri hesablayın:

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

C_{n-1}^{k-1} + C_{n-1}^{k} = {(n - 1)! \over (k - 1)! \cdot (n - k)!} + {(n - 1)! \over k! \cdot (n - k - 1)!} =

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

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

Eolymp #3260. Neçə?

Riyazi analiz imtahanına hazırlaşarkən, Petyanın qarşısında $n$ müxtəlif yazıqlar var idi. Onlar onun xilas yolu idi, çünki bütün semestr boyunca Petya materialı düzgün öyr

ənməyə cəhd etməmişdi. Yazıqlar o qədər çox idi ki, onlar heç bir cibə yerləşmirdi. Buna görə Petya imtahana öz ilə götürə biləcəyi maksimum yazıq sayını hesablamağa qərar verdi. Və burada bir sual meydana çıxdı: ümumiyyətlə lazımi yazıqların sayını seçmənin neçə yolu var?

Giriş məlumatları. Ümumi yazıq sayı $n (1 \leq n \leq 12)$ n~(1 \le n \le 12) və Petyanın özü ilə götürə biləcəyi yazıq sayı $k (0 \leq k \leq n)$ k~(0 \le k \le n) verilmişdir.

Çıxış məlumatları. $n$ yazıqdan $k$ yazıq seçmənin yollarının sayını çıxarın.

Məsələni aç

Cnk funksiyası binomial əmsalın qiymətini iterativ metodla hesablayır.

int Cnk(int n, int k)
{
  int res = 1;
  for(int i = 1; i <= k; i++)
    res = res * (n - i + 1) / i;
  return res;
}

C++

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

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

Cavabı hesablayın və çıxarın.

res = Cnk(n,k);
printf("%d\n",res);

Cnk funksiyası binomial əmsalın qiymətini rekursiv metodla hesablayır.

int Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  return Cnk(n - 1, k - 1) + Cnk(n - 1, k);
}

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

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

Cavabı hesablayın və çıxarın.

res = Cnk(n,k);
printf("%d\n",res);

Eolymp #5329. Axşam

$n$ LKS-lər arasında neçə nəfər kefir alacağını seçmək üçün neçə yol var? Cavabı $9929$ -a bərabər olaraq çıxarın.

Giriş məlumatları. $n$ və $k (0 \leq k \leq n \leq 500)$ k~(0 \le k \le n \le 500) tam ədədləri.

Çıxış məlumatları. Cavabı $9929$ -a bərabər olaraq çıxarın.

Məsələni aç

Sabitləri və $c nk$ massivini elan edək, burada $c nk [n] [k] = C_{n}^{k} m o d 9929$ cnk[n][k] = C_n^{k}~mod~9929.

#define MAX 510
#define MOD 9929
int cnk[MAX][MAX];

c funksiyası $C_{n}^{k} m o d 9929$ C_n^{k}~mod~9929 binomial əmsalın qiymətini hesablayır.

int c(int n, int k)
{
  if (cnk[n][k] > 0) return cnk[n][k];
  if (n - k < k) return c(n,n-k);
  if (!k) return cnk[n][k] = 1;
  return cnk[n][k] = (c(n-1,k) + c(n-1,k-1)) % MOD;
}

C++

Proqramın əsas hissəsi. $c nk$ massivini sıfırla yükləyin. Giriş məlumatlarını oxuyun.

memset(cnk,0,sizeof(cnk));
scanf("%d %d",&n,&k);

Cavabı hesablayın və çıxarın.

printf("%d\n",c(n,k));

Binomial əmsallar Nyuton binomunda görünür:

(x + y)^{n} = k = 0 \sum n C_{n}^{k} x^{k} y^{n - k}

(x + y)^n = \sum_{k=0}^n C_n^{k}x^{k}y^{n-k}

Nümunələri nəzərdən keçirək:

(x + y)^{2} = C_{2}^{0} x^{2} y^{0} + C_{2}^{1} x^{1} y^{1} + C_{2}^{2} x^{0} y^{2} = x^{2} + 2 x y + y^{2},

(x + y)^2 = C_2^{0}x^{2}y^{0} + C_2^{1}x^{1}y^{1} + C_2^{2}x^{0}y^{2} = x^2 + 2xy + y^2,

(x + y)^{3} = C_{3}^{0} x^{3} y^{0} + C_{3}^{1} x^{2} y^{1} + C_{3}^{2} x^{1} y^{2} + C_{3}^{3} x^{0} y^{3} = x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3}

(x + y)^3 = C_3^{0}x^{3}y^{0} + C_3^{1}x^{2}y^{1} + C_3^{2}x^{1}y^{2} + C_3^{3}x^{0}y^{3} = x^3 + 3x^2y + 3xy^2 + y^3

Eolymp #9892. C0n + ... + Cnn

Verilmiş qeyri-mənfi tam ədəd $n$ üçün binomial əmsalların cəmini tapın

C_{n}^{0} + C_{n}^{1} + ... + C_{n}^{n}

C_n^{0} + C_n^{1} + ... + C_n^{n}

Giriş məlumatları. Bir qeyri-mənfi tam ədəd $n (n \leq 60)$ n~(n \le 60).

Çıxış məlumatları. Cəmin qiymətini çıxarın.

Məsələni aç

Eolymp #11271. Cnk kvadratlarının cəmi

Verilmiş qeyri-mənfi tam ədəd $n$ üçün binomial əmsalların kvadratlarının cəmini tapın

(C_{n}^{0})^{2} + (C_{n}^{1})^{2} + (C_{n}^{2})^{2} + ... + (C_{n}^{n})^{2}

(C_n^{0})^2 + (C_n^{1})^2 + (C_n^{2})^2 + ... + (C_n^{n})^2

Giriş məlumatları. Bir qeyri-mənfi tam ədəd $n (n \leq 30)$ n~(n \le 30).

Çıxış məlumatları. Cəmin qiymətini çıxarın.

Məsələni aç

Cnk funksiyası $C_{n}^{k}$ C_n^k binomial əmsalının qiymətini hesablayır.

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

C++

Proqramın əsas hissəsi. Giriş dəyəri $n$ -i oxuyun.

scanf("%lld", &n);

Cavabı hesablayın və çıxarın.

res = Cnk(2*n, n);
printf("%lld\n", res);

Eolymp #11550. x1 + x2 + ... + xk = n

Verilmiş $k$ və $n$ dəyərlərinə görə aşağıdakı tənliyin natural həllərinin sayını tapın

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

x_1 + x_2 + ... + x_k = n

Giriş məlumatları. İki natural ədəd $k$ və $n (k \leq n \leq 100)$ n~(k \le n \le 100).

Çıxış məlumatları. Verilmiş tənlik üçün natural həllərin sayını çıxarın. Məlumdur ki, cavab $1 0^{18}$ 10^{18}-i keçmir.

Məsələni aç

Cnk funksiyası $C_{n}^{k}$ C_n^k binomial əmsalının qiymətini hesablayır.

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

C++

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

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

$C_{n - 1}^{k - 1}$ C_{n-1}^{k-1} cavabını hesablayın və çıxarın.

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

Eolymp #11551. x1+...+xk = n (2)

Verilmiş $k$ və $n$ dəyərlərinə görə aşağıdakı tənliyin qeyri-mənfi tam ədəd həllərinin sayını tapın

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

x_1 + x_2 + ... + x_k = n

Giriş məlumatları. İki natural ədəd $k$ və $n (k \leq n \leq 100)$ n~(k \le n \le 100).

Çıxış məlumatları. Verilmiş tənlik üçün qeyri-mənfi tam ədəd həllərinin sayını çıxarın. Məlumdur ki, cavab $1 0^{18}$ 10^{18}-i keçmir.

Məsələni aç

Cnk funksiyası $C_{n}^{k}$ C_n^k binomial əmsalının qiymətini hesablayır.

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

C++

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

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

$C_{n + k - 1}^{k - 1}$ C_{n+k-1}^{k-1} cavabını hesablayın və çıxarın.

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

Eolymp #318. Binomial əmsallar 1

$n$ qeyri-mənfi tam ədəd olsun. Göstərək ki,

n! = 1 \cdot 2 \cdot ... \cdot n (0! = 1),

n! = 1 \cdot 2 \cdot ... \cdot n~(0! = 1),

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

C_n^{k} = {n! \over k! \cdot (n - k)!} (0 \le k \le n)

Verilmiş $n$ və $k$ üçün $C_{n}^{k}$ C_n^{k}-nin qiymətini hesablayın.

Giriş məlumatları. Birinci sətir testlərin sayını $t (t \leq 50)$ t~(t \le 50) ehtiva edir. Növbəti $t$ sətirin hər biri iki tam ədəd $n$ və $k (0 \leq n < 2^{64}, 0 \leq C_{n}^{k} < 2^{64})$ k~(0 \le n < 2^{64}, 0 \le C_n^{k} < 2^{64}) ehtiva edir.

Çıxış məlumatları. Hər bir test üçün $C_{n}^{k}$ C_n^{k} dəyərini ehtiva edən $t$ sətir çıxışa verin.

Məsələni aç

Hesablamalar $64$ bitlik işarəsiz tam ədədlərdən (unsigned long long) istifadə edilərək aparılacaq. 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 n - 2 \cdot 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 \cdot 3} \cdot ... \cdot {n - k + 1 \over k}

Dəyişən $r es$ -ə $1$ qiyməti verin, sonra isə onu $i = 1$ i = 1-dən $k$ -yə qədər bütün $n - i + 1/ i$ n - i + 1 / i-ə vurun. Hər dəfə bölmə tam ədədli olacaq, lakin vurma zamanı yüklənmə baş verə bilər. $d = r es v ə i - nin ə nb o ¨ y u ¨ k or t a q b o ¨ l ə ni$ d = res və i-nin ən böyük ortaq böləni olsun. Onda əməliyyat

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

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

aşağıdakı kimi yazılsın

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

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

Bu tətbiqlə vurma zamanı yüklənmə baş verməyəcək (cavab $64$ bitlik işarəsiz tam ədəddir). Əvvəlcə $(n - i + 1) / (i / d)$ (n – i + 1 ) / (i / d) bölməsini, sonra isə $r es / d$ -i əldə edilmiş qismətə vurmağı unutmayın.

$C_{n}^{k}$ C_n^k-nı hesablamaq üçün $k$ iterasiya yerinə yetirmək lazımdır. Lakin $C_{2000000000}^{1999999999}$ C_{2000000000}^{1999999999}-u hesablamaq lazım gələrsə nə etməli? Cavab $2^{64}$ 2^{64}-ü keçməyəcək, ona görə də belə giriş məlumatları mümkündür. $C_{n}^{k} = C_{n}^{n - k}$ C_n^k = C_n^{n - k} olduğuna görə $n - k < k$ n – k < k olduqda $k = n - k$ k = n – k qəbul edilməlidir.

Nümunə

Aşağıdakı nümunəni 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}

$15 * \frac{4}{3}$ 15 * {4 \over 3} vurması qalıb. $d = 15 v ə3 - u ¨ n ə nb o ¨ y u ¨ k or t a q b o ¨ l ə ni = 3$ d = 15 və 3-ün ən böyük ortaq böləni = 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.

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 qiymətini 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++)
  {

Növbəti iterasiyada nəticə $m$ -i keçərsə (məsələni həll etmək üçün $C_{n}^{k} = m$ C_n^k = m tənliyini axtarırıq), dayanırıq. Bu funksiyadan çıxmaqla yüklənmədən də qaçırıq.

    if (1.0 * Res * (n - i + 1) / i > m) return m + 1;
    Res = Res * (n - i + 1) / i;
  }
  return Res;
}

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

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

C++

Eolymp #11488. Binomial cəm

Verilmiş natural ədəd $n$ . Aşağıdakı cəmin qiymətini tapın

1 \cdot C_{n}^{0} + 2 \cdot C_{n}^{1} + 3 \cdot C_{n}^{2} + ... + (n + 1) \cdot C_{n}^{n}

1 \cdot C_n^{0} + 2 \cdot C_n^{1} + 3 \cdot C_n^{2} + ... + (n + 1) \cdot C_n^{n}

Giriş məlumatları. Bir natural ədəd $n (n \leq 30)$ n\:(n \le 30).

Çıxış məlumatları. Axtarılan cəmin qiymətini çıxarın.

Məsələni aç

Giriş dəyəri $n$ -i oxuyun.

scanf("%lld", &n);

Cavabı hesablayın və çıxarın.

res = (1LL << (n - 1)) * (n + 2);
printf("%lld\n", res);

Alqoritmin tətbiqi – funksiya

Nəticələri yadda saxlamaq üçün massiv təyin edin: $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

int dp[31][31];

Cnk funksiyası $C_{n}^{k}$ C_n^k binomial əmsalının qiymətini hesablayır.

int 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)) % 9929;
}

C++

Proqramın əsas hissəsi. Giriş dəyəri $n$ -i oxuyun.

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

Göstərilən cəmi hesablayın.

res = 0;
for (i = 0; i <= n; i++)
  res += (i + 1) * Cnk(n, i);

Cavabı çıxarın.

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

Eolymp #10668. Şəbəkə üzərində yollar

Sizdə bir parça kağız var və onda $n \cdot m$ n \cdot m ölçüsündə düzbucaqlı seçirsiniz. Bu düzbucaqlını, onun üzərində yerləşən xətlər ilə birlikdə, şəbəkə adlandıraq. Şəbəkənin sol alt küncündən başlayaraq, karandaşınızı sağ üst küncə hərəkət etdirirsiniz, xətlər üzərində qalaraq yalnız sağa və ya yuxarı hərəkət edirsiniz. Nəticə solda göstərilmişdir:

Həqiqətən bir şah əsər deyilmi? Proseduru yenidən təkrarlayaraq, sağda göstərilmiş şəkildə nəticə əldə edəcəksiniz. İndi isə sual yaranır: bu üsulla neçə fərqli sənət əsəri yaratmaq olar?

Giriş məlumatları. İki təbii ədəd $n$ və $m$ .

Çıxış məlumatları. Yuxarıda təsvir olunan prosedurdan istifadə edərək yaratmaq mümkün olan müxtəlif sənət əsərlərinin sayını çıxarın. Bu sayın $64$ bitlik işarəli tam ədədə uyğun gəldiyini deyə bilərik.

Məsələni aç

Cnk funksiyası binomial əmsalın qiymətini hesablayır.

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

C++

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

scanf("%lld %lld", &n, &m);

$C_{n + m}^{n}$ C_{n+m}^n cavabını hesablayın və çıxarın.

res = Cnk(n + m, n);
printf("%lld\n", res);

Eolymp #4008. Binomial əmsallar

Gunnar kifayət qədər yaşlı və unutqan bir tədqiqatçıdır. Hazırda o, sosial şəbəkələrdə təhlükəsizlik mövzusunda məqalə yazır və bu məqalədə bəzi kombinatorika elementləri də yer alır. O, bəzi hesablamaları yoxlamaq üçün binomial əmsalların hesablanması üçün proqram yazıb.

Binomial əmsal $C_{n}^{k}$ C_n^{k} bu ədəddir

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

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

$n$ və $k$ qeyri-mənfi ədədlərdir.

Gunnar proqramından istifadə edərək $C_{n}^{k}$ C_n^{k}-ni hesablayıb və nəticədə $m$ ədədini alıb. Təəssüf ki, unutqan olduğuna görə, o, giriş kimi istifadə etdiyi $n$ və $k$ ədədlərini unudub. Bu iki ədəd uzun hesablamaların nəticəsi idi və onlar masasının üzərində olan çoxsaylı kağızlardan birində yazılmışdı. Kağızlarda axtarmaq əvəzinə, o, alınan cavabdan $n$ və $k$ ədədlərini bərpa etməyə qərar verdi. Ona bütün mümkün qiymətləri tapmaqda kömək edə bilərsinizmi?

Giriş məlumatları. Birinci sətir testlərin sayını, ən çox $100$ , ehtiva edir. Hər test bir sətirdə verilir və Gunnarın proqramının nəticəsi olan $m (2 \leq m \leq 1 0^{15})$ m~(2 \le m \le 10^{15}) tam ədədini ehtiva edir.

Çıxış məlumatları. Hər test üçün iki sətir çap edin. Birinci sətir $m$ ədədini binomial əms

aldan ifadə etməyin üsullarının sayını ehtiva etməlidir. İkinci sətirdə $C_{n}^{k} = m$ C_n^{k} = m şərtini ödəyən bütün $(n, k)$ cütləri olmalıdır. Cütlər $n$ artan sırası ilə və $k$ artan sırası ilə yerləşdirilməlidir. Cütlərin çap formatı nümunədə göstərilmişdir.

Məsələni aç

Axtarılan cütləri cütlər vektorunda saxlayaq.

vector<pair<long long,long long> > res;

Cnk funksiyası $C_{n}^{k}$ C_n^k binomial əmsalının qiymətini hesablayır.

long long Cnk(long long n, long long k)
{
  long long i, Res = 1;
  if (k > n - k) k = n - k;
  for(i = 1; i <= k; i++)
  {

    if (1.0 * Res * (n - i + 1) / i > m) return m + 1;
    Res = Res * (n - i + 1) / i;
  }
  return Res;
}

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

scanf("%d",&tests);
while (tests--) 
{
  res.clear();
  scanf("%lld",&m);

$k$ dəyərini $C_{2 k}^{k} \leq m$ C_{2k}^k ≤ m qədər nəzərdən keçirin.

  for(k = 0; Cnk(2*k,k) <= m; k++)
  {

$2 k \leq n \leq m$ 2k \le n \le m aralığında $n$ dəyərini ikili axtarışla tapın.

    long long lo = 2*k, hi = m;
    while (lo < hi) 
    {
      long long n = (lo + hi) / 2;
      if (Cnk(n,k) < m) lo = n + 1; else hi = n;
    }

$C_{l o}^{k} = m$ C_{lo}^k = m olduqda həll tapılır. Nəticəyə bir və ya iki cüt həll daxil edin.

    if (Cnk(lo,k) == m)
    {
      res.push_back(make_pair(lo,k));
      if (lo != 2*k)
        res.push_back(make_pair(lo,lo - k));
    }
  }

C++

Cütləri sırala.

  sort(res.begin(),res.end());

Cavabı çıxarın - tapılan cütlərin sayını və cütləri.

  printf("%d\n",res.size());
  for(i = 0; i < res.size(); i++)
    printf("(%lld,%lld) ", res[i].first,res[i].second);
  printf("\n");
}

Binomial əmsal üçün asimptotik qiymətləndirmələr

Teorema 1. Binomial əmsallar arasında belə bir əlaqə var:

C_{n}^{0} < C_{n}^{1} < ... < C_{n}^{⌊ n /2 ⌋} \geq C_{n}^{⌊ n /2 ⌋ + 1} > ... > C_{n}^{n}

C_n^0 < C_n^1 < ... < C_n^{\lfloor n/2 \rfloor} \ge C_n^{\lfloor n/2 \rfloor + 1} > ... > C_n^n

Teorema 2. $C_{2 n}^{n} < 4^{n}$ C_{2n}^n < 4^n. Bu ondan irəli gəlir ki, $\sum_{k = 0}^{2 n} C_{2 n}^{k} = (1 + 1)^{2 n} = 2^{2 n} = 4^{n}$ \sum_{k = 0}^{2n} C_{2n}^k = (1 + 1)^{2n} = 2^{2n} = 4^n

Teorema 3. $C_{2 n}^{n} > \frac{4 ^{n}}{2 n + 1}$ C_{2n}^n > {4^n \over 2n + 1}. Bu ondan irəli gəlir ki, $\sum_{k = 0}^{2 n} C_{2 n}^{k} = 4^{n}$ \sum_{k = 0}^{2n} C_{2n}^k = 4^n, və əmsallar $2 n + 1$ 2n + 1-dir. Buna görə daha böyük əmsal $\frac{4 ^{n}}{2 n + 1}$ {4^n \over 2n + 1}-dən çox olacaq.

Teorema 4. Stirlinq formulu. $n! \approx 2 π n (\frac{n}{e})^{n}$ n! ≈ \sqrt{2 \pi n}\left({n \over e} \right) ^ n.

Daha dəqiq təxmini formulu:

n! \approx 2 π n (\frac{n}{e})^{n} (1 + \frac{1}{12 n} + \frac{1}{288 n ^{2}} - \frac{139}{51849 n ^{3}} - \frac{571}{2488320 n ^{4}})

n! ≈ \sqrt{2 \pi n} \left({n \over e} \right) ^ n \left( 1 + {1 \over 12n} + {1 \over 288n^2} - {139 \over 51849n^3} - {571 \over 2488320n^4} \right)

Teorema 5.

C_{2 n}^{n} \approx \frac{4 π n ( \frac{2 n}{e} ) ^{2 n}}{( 2 π n ( \frac{n}{e} ) ^{n} ) ^{2}} = \frac{4 ^{n}}{π n}

C_{2n}^n ≈ {\sqrt{4 \pi n}\left({2n \over e} \right) ^ {2n} \over \left( \sqrt{2 \pi n}\left({n \over e} \right) ^ n \right) ^2} = {4^n \over \sqrt{\pi n}}

Teorema 6.

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

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

\frac{n !}{k !} \cdot (1 - \frac{1}{n}) \cdot (1 - \frac{2}{n}) \cdot ... \cdot (1 - \frac{k - 1}{n}) =

{n! \over k!} \cdot \left( 1 - {1 \over n} \right) \cdot \left( 1 - {2 \over n} \right) \cdot ... \cdot \left( 1 - {k - 1 \over n} \right) =

\frac{n !}{k !} \cdot e^{l n (1 - \frac{1}{n}) + l n (1 - \frac{2}{n}) + ... + l n (1 - \frac{k - 1}{n})} \leq (l n (1 - x) \leq - x n e q a l i v a s i t ə s i l ə)

{n! \over k!} \cdot e ^{ln \left( 1 - {1 \over n} \right) + ln \left( 1 - {2 \over n} \right) + ... + ln \left( 1 - {k - 1 \over n} \right)} \le (ln(1 - x) \le -x~neqali~vasitəsilə)

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

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

Binomial əmsalı

Binomial əmsal üçün asimptotik qiymətləndirmələr

İstifadə olunan məsələlərin siyahısı

Şərhlər