9890. Balls and boxes

Find the number of ways to put n different balls into k boxes. Each box can contain any number of balls, including zero.

Input. Two positive integers n and k.

Output. Print the number of ways to put n different balls into k boxes. It is guaranteed that this number does not exceed 10¹⁸.

Sample input	Sample output
2 2	4

SOLUTION

combinatorics

Algorithm analysis

Let’s consider the first ball. It can be placed in one of the k available boxes. Thus, there are k options for placing the first ball. Similarly, each subsequent ball can also be placed in one of the k boxes (there are k options for each ball).

Therefore, the total number of ways to distribute all the balls into the boxes is the product k * k * … * k = kⁿ.

Example

Let’s say we have two balls numbered 1 and 2, as well as two boxes numbered 1 and 2. In this case, the balls can be distributed into the boxes in the following four ways:

Algorithm implementation

Read the input data.

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

Compute res = kⁿ.

res = 1;

for (i = 1; i <= n; i++)

res = res * k;

Print the answer.

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