Paths on a Grid#10668

Paths on a Grid (Editorial)

The required path is a broken line consisting of $n + m$ n + m links. Of these, $n$ links must be vertical, and the rest must be horizontal. The number of ways to choose $n$ vertical links out of $n + m$ n + m is equal to $C_{n + m}^{n}$ C_{n+m}^n.

Example

For the first test case $n = 3, m = 4$ n = 3, m = 4. The answer is $C_{7}^{3} = \frac{7 !}{3 ! \cdot 4 !} = \frac{7 \cdot 6 \cdot 5}{1 \cdot 2 \cdot 3} = 35$ C_7^3 = {7! \over 3! \cdot 4!} = {7 \cdot 6 \cdot 5 \over 1 \cdot 2 \cdot 3} = 35.

For the second test case $n = 1, m = 1$ n = 1, m = 1. The answer is $C_{2}^{1} = \frac{2 !}{1 ! \cdot 1 !} = 2$ C_2^1 = {2! \over 1! \cdot 1!} = 2.

Algorithm realization

The function Cnk computes the value of the binomial coefficient $C_{n}^{k}$ C_n^k.

long long Cnk(long long n, long long k)
{
  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;
}

C++

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

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

Compute and print the answer $C_{n + m}^{n}$ C_{n+m}^n.

res = Cnk(n + m, n);
printf("%lld\n", res);

Python realization

import math

Read the input data.

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

Compute and print the answer $C_{n + m}^{n}$ C_{n+m}^n.

res = math.comb(n + m, n)
print(res)