Editorial

Consider a sequence of $n+k-1$ positions. In $n$ positions we should place $1$. In $k-1$ positions we should place the '$+$' symbol (to obtain $k$ terms).

Any arrangement of $1$s and '$+$' signs among these positions will correspond to some solution of the given equation. For example, consider some solutions of the equation $x_1+x_2+x_3=4(4$ ones and $2$ plus signs):

We should insert $k-1$ plus signs into $n+k-1$ positions. This can be done in $C_{n+k-1}^{k-1}$ ways.

Example

Consider the equation $x_1+x_2+x_3=4$. Its solutions are:

• $(4,0,0)$ and its $3$ permutations

• $(3,1,0)$ and its $6$ permutations'

• $(2,2,0)$ and its $3$ permutations

• $(2,1,1)$ and its $3$ permutations

There are $3+6+3+3=15$ solutions.

Algorithm implementation

The Cnk function computes the value of the binomial coefficient $C_n^k$.

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;
}

The main part of the program. Read the input data.

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

Compute and print the answer — the value of $C_{n+k-1}^{k-1}$.

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

Python implementation

import math

Read the input data.

k, n = map(int,input().split())

Вычисляем и выводим ответ $C_{n+k-1}^{k-1}$.

res = math.comb(n + k - 1, k - 1)
print(res)