Разбор

Испытание Бернулли — это эксперимент с двумя возможными исходами:

Успех (событие происходит) с вероятностью $p$ ,
Неудача (событие не происходит) с вероятностью $1 - p$ .

Испытание называется "бернуллиевским", если оно независимое и вероятность его успеха остаётся постоянной на протяжении всех испытаний.

Схема испытаний Бернулли — это серия независимых испытаний, каждое из которых является испытанием Бернулли. Обозначим количество испытаний через $n$ . В каждом испытании вероятность успеха $p$ и неудачи $1 - p$ остаются неизменными.

Примером может служить многократное подбрасывание монеты. Если нас интересует, сколько раз выпадет орел из $n$ подбрасываний, то это и будет схема испытаний Бернулли.

Число успехов в серии из $n$ испытаний Бернулли подчиняется биномиальному распределению. Пусть $X$ — случайная величина, которая обозначает число успехов в $n$ испытаниях. Тогда:

P (X = k) = C_{n}^{k} \cdot p^{k} \cdot (1 - p)^{n - k}

где

$p$ — вероятность успеха в каждом испытании,
$k$ — количество успехов из $n$ испытаний.

Для вычисления значения биномиального коэффициента в действительных числах воспользуемся следующим приемом:

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

Известно, что $l n n! = l n (1 \cdot 2 \cdot ... \cdot n) = l n 1 + l n 2 + ... + l n n$

Значения $l n i!$ запоминаем в ячейках массива $l f [i]$ . Далее вычисляем

res = l n n! - l n k! - l n (n - k)! = l f [n] - l f [k] - l f [n - k],

после чего

C_{n}^{k} = e^{res}

Пример

В первом тесте проводится $n = 8$ испытаний. Вероятность наступления события $А$ в каждом испытании равна $p = 0.3$ . Мы хотим найти вероятность того, что событие $А$ произойдет ровно $k = 2$ раза. Искомая вероятность равна:

P (X = 2) = C_{8}^{2} \cdot 0. 3^{2} \cdot 0. 7^{6} \approx 0.296475

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

Объявим рабочий массив $l f$ , где $l f [i] = l n i! = l n 1 + l n 2 + ... + l n i$ .

#define MAX 1001
double lf[MAX];

Читаем входные данные.

scanf("%d %d", &n, &k);
scanf("%lf", &p);
q = 1 - p;

Заполняем массив $l f$ .

lf[1] = 0;
for (i = 2; i <= n; i++)
  lf[i] = lf[i - 1] + log(i);

Вычисляем значение биномиального коеффициента $res = C_{n}^{k}$ .

res = lf[n] - lf[k] - lf[n - k];
res = exp(res);

Вычисляем ответ $res = C_{n}^{k} \cdot p^{k} \cdot (1 - p)^{n - k}$ .

for (i = 0; i < k; i++)
  res = res * p;
for (i = 0; i < n - k; i++)
  res = res * q;

Выводим ответ.

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