Паскалийн гурвалжныг мөр мөрөөр бөглөж, n зүйлээс k-г сонгох аргын тоог олно. Хариуг m-д хуваасан үлдэгдлээр нь хадгална.

Pre-IntermediateХугацаа: O(n²)Санах ой: O(n²)
HackerRank дээр бодох

Эхлээд жижиг бодлого

4 найзаас 2-ыг хэдэн янзаар сонгох вэ? Паскалийн гурвалжны мөрүүд: 1, 1 1, 1 2 1, 1 3 3 1, 1 4 6 4 1.

Мөр, байрлалыг 0-ээс тоолоход 4-р мөрийн 2-р байрлалд 6 байна. Тиймээс C(4, 2) = 6. Нүд бүр дээрх хоёр нүдний нийлбэр: 6 = 3 + 3.

Энгийн аргаас санаа руу

Томьёо n! / (k! (n − k)!) нь хурдан ч n = 30 үед 30! нь long long-д ч багтахгүй. Бүх сонголтыг жагсааж тоолох нь бүр удаан.

Эхний зүйлийг сонгох уу, үгүй юу гэж хоёр тохиолдолд хуваавал C(n, k) = C(n − 1, k − 1) + C(n − 1, k). Зөвхөн нэмэх үйлдэл ашигладаг тул нэмэх бүрт % m авахад хангалттай, хуваах шаардлагагүй.

Нэр томьёо ба тэмдэглэгээ

C(n, k)
n зүйлээс k-г сонгох аргын тоо. Дараалал хамаарахгүй.
C[i][j]
Хүснэгтийн нүд: C(i, j) mod m.
m
Модуль. Ихэвчлэн 10⁹ + 7.
Паскалийн гурвалжин
Мөр бүр нь C(i, 0) … C(i, i). Захын нүднүүд 1, бусад нь дээрх хоёрын нийлбэр.
i \ j0123450
1
2
3
4
5
n = 5k = 2m = 1000000007

C(5, 2) нь 5 зүйлээс 2-ыг хэдэн янзаар сонгож болохыг заана. Паскалийн гурвалжныг мөр мөрөөр бөглөнө: нүд бүр дээрх хоёр нүдний нийлбэр. Хариуг 1000000007-д хуваасан үлдэгдлээр нь хадгална.

Алхам 1 / 23
Хурд
  • Нэмж буй хоёр нүд
  • Сая бөглөсөн
  • Хайж буй C[n][k]
  • Хариу
Слайд 1 / 6

Хэдэн янзаар сонгох вэ?

5 найзаасаа 2-ыг хэдэн янзаар сонгох вэ? Энэ тоог C(5, 2) гэж тэмдэглэнэ. Паскалийн гурвалжнаар бодъё.

binomial-coefficients.cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, m, C[1005][1005];
int main() {
cin >> n >> k >> m;
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;
}
}
cout << C[n][k] << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

«n зүйлээс k-г хэдэн янзаар сонгох вэ?» гэсэн асуултад хариулна. Тоолох бодлого, DP бодлогод байнга гардаг. Тоо хурдан томордог тул m-д хуваасан үлдэгдлийг нь хадгална.

Яаж ажилладаг вэ?

1. C[i][0] = 1: юу ч сонгохгүй байх ганц л арга бий. 2. C[i][j] = C[i − 1][j − 1] + C[i − 1][j]: эхний зүйлийг сонгох, сонгохгүй байх хоёр тохиолдлын нийлбэр. 3. Хариу их томордог тул нэмэх бүрт % m авна. 4. Хүснэгтийг i = 0 … n мөрөөр бөглөөд C[n][k]-г хэвлэнэ. Оролт: n, k, m.

Яагаад зөв, хэр хурдан бэ?

n зүйлээс k-г сонгох арга бүр эхний зүйлийг агуулах эсвэл агуулахгүй. Агуулбал үлдсэн n − 1-ээс k − 1-ийг, агуулахгүй бол k-г сонгоно. Хоёр бүлэг давхцахгүй тул нийлбэр нь яг хариу. Захын нүд C[i][0] = 1, харин j > i нүд 0.

Хүснэгт (n + 1)²/2 нүдтэй, нүд бүрт нэг нэмэх үйлдэл: O(n²) хугацаа ба санах ой. n = 5000 бол 12.5 сая нүд. Олон асуулттай бол хүснэгтийг нэг удаа бөглөөд асуулт бүрт O(1)-д хариулна.

Түгээмэл алдаа

  • Нэмэх бүрт % m авахгүй байх. C(1000, 500) нь 300 орчим оронтой тоо тул long long-д багтахгүй.
  • C[i][j]-д j > i нүдийг санамсаргүй утгатай үлдээх. Глобал array 0-ээр эхэлдэг ч local array-г заавал 0 болго.
  • n = 10⁶ шиг том n-д хүснэгт ашиглах. n² санах ой багтахгүй. Тэр үед factorial ба Modular Inverse ашигладаг.

Хязгаарын тохиолдол

  • k = 0 эсвэл k = n: хариу 1.
  • n = 0: ганц нүд C[0][0] = 1.
  • m = 2: үлдэгдэл нь 0 эсвэл 1 тул хүснэгт Серпинскийн гурвалжин шиг зураг үүсгэнэ.

Өөрийгөө шалга

  1. C(6, 3) хэд вэ?

    Хариу харах

    20.

  2. 5-р мөрийн тоонуудын нийлбэр хэд вэ?

    Хариу харах

    32 = 2⁵. Мөр бүрийн нийлбэр 2-ын зэрэг, учир нь зүйл бүрийг авах эсвэл авахгүй.

  3. C(10, 5) mod 2 хэд вэ?

    Хариу харах

    0. C(10, 5) = 252 тэгш тоо.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.Паскалийн гурвалжны 6-р мөрийг бөглө.

    Hint харах

    5-р мөр нь 1 5 10 10 5 1.

    Хариу ба тайлбар

    1 6 15 20 15 6 1.

  2. 2.10-р мөрийн хэдэн тоо сондгой вэ?

    Hint харах

    m = 2 үед хүснэгтийг бөглөөд 1-ийг тоол.

    Хариу ба тайлбар

    4: C(10, 0), C(10, 2), C(10, 8), C(10, 10). Ерөнхийдөө 2^(n-ийн хоёртын бичлэг дэх 1-ийн тоо).

  3. 3.Хоёр хэмжээст хүснэгтийн оронд нэг хэмжээст array-гээр C(n, k)-г бод.

    Hint харах

    Мөр шинэчлэхдээ j-г баруунаас зүүн тийш яв.

    Хариу ба тайлбар

    C[0] = 1; for i = 1..n: for (j = i; j >= 1; j--) C[j] = (C[j] + C[j - 1]) % m; Санах ой O(n). Зүүнээс явбал шинэчилсэн утгаа дахин ашиглаж буруу болно.

Жишээ

Оролт

5 2 1000000007

Гаралт

10

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.