Redaksiya

Consider a sequence of $n$ ones: $\mathrm{111...11}$. You can insert a ‘$+$’ sign between any two ones. For example, $11+111+1$. Such notation denotes the sum $2+3+1$, where each term represents the number of ones adjacent to each other. The number of positions where a ‘$+$’ sign can be inserted is $n–1$. Since the sum must consist of $k$ terms, $k–1$ ‘$+$’ signs should be inserted.

We should insert $k–1$ pluses in $n–1$ places. This can be done in $C_{n-1}^{k-1}$ ways.

Example

Consider the equation $x_1+x_2+x_3=4$. It has $3$ positive integer solutions: $(1,1,2),(1,2,1),(2,1,1)$.

For example, $n=4$ ones can be divided into $k=3$ terms in $C_2^3=3$ ways:

Algorithm realization

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-1}^{k-1}$.

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

Python реализация

import math

Read the input data.

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

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

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