Editorial

A Bernoulli trial is an experiment with two possible outcomes:

Success (the event occurs) with probability $p$ ,
Failure (the event does not occur) with probability $1 - p$ .

A trial is called "Bernoulli" if it is independent and the probability of success remains constant throughout all trials.

The Bernoulli trial scheme is a series of independent trials, each of which is a Bernoulli trial. Let the number of trials be denoted by $n$ . In each trial, the probability of success is $p$ and the probability of failure is $1 - p$ , and these probabilities remain constant.

An example could be repeatedly flipping a coin. If we are interested in how many times heads will appear out of $n$ flips, this would represent a Bernoulli trial scheme.

The number of successes in a series of $n$ Bernoulli trials follows a binomial distribution. Let $X$ be a random variable representing the number of successes in $n$ trials. Then:

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

where

$p$ is the probability of success in each trial,
$k$ is the number of successes out of n trials.

To compute the value of the binomial coefficient with real numbers, we will use the following approach:

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

It is known that $l n n! = l n (1 \cdot 2 \cdot ... \cdot n) = l n 1 + l n 2 + ... + l n n$

Store the values of $l n i!$ in the cells of an array $l f [i]$ . Then we calculate

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

After that

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

Example

In the first test, $n = 8$ trials are conducted. The probability of event $A$ occurring in each trial is $p = 0.3$ . We want to find the probability that event A occurs exactly $k = 2$ times. The desired probability is:

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

Algorithm realization

Declare an array $l f$ , where $l f [i] = l n i! = l n 1 + l n 2 + ... + l n i$ .

#define MAX 1001
double lf[MAX];

Read the input data.

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

Fill the array $l f$ .

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

Compute the value of the binomial coefficient $res = C_{n}^{k}$ .

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

Compute the answer $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;

Print the answer.

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