Two arrays#11725

Two arrays (Editorial)

Let us consider the combined sequence:

a_{1}, a_{2}, ..., a_{m}, b_{m}, b_{m - 1}, ..., b_{1}

a_1, a_2, ..., a_m, b_m, b_{m - 1}, ..., b_1

Its length is $2 m$ . From the problem conditions, it follows that this sequence:

is sorted in nondecreasing order;
consists of integers from $1$ to $n$ .

Thus, the problem reduces to counting the number of nondecreasing sequences

1 \leq x_{1} \leq x_{2} \leq ... \leq x_{2 m} \leq n

1 \le x_1 \le x_2 \le ... \le x_{2m} \le n

Let us perform a change of variables:

y_{1} = x_{1} - 1, y_{2} = x_{2} - x_{1}, y_{3} = x_{3} - x_{2}, ..., y_{2 m} = x_{2 m} - x_{2 m - 1}, y_{2 m + 1} = n - x_{2 m}

y_1 = x_1 - 1, \\ y_2 = x_2 - x_1, \\ y_3 = x_3 - x_2, \\ ..., \\ y_{2m} = x_{2m} - x_{2m-1}, \\ y_{2m+1} = n - x_{2m}

Then all $y_{i} \geq 0$ y_i \ge 0, and their sum is

y_{1} + y_{2} + ... + y_{2 m} + y_{2 m + 1} = n - 1

y_1 + y_2 + ... + y_{2m} + y_{2m+1} = n - 1

Therefore, the problem reduces to counting the number of ways to decompose the number $n - 1$ n - 1 into $2 m + 1$ 2m + 1 non-negative integers. Each such decomposition corresponds to exactly one nondecreasing sequence $x_{1}, x_{2}, ..., x_{2 m}$ x_1, x_2, ..., x_{2m}, and hence to exactly one pair of arrays $(a; b)$ .

By the classical formula for combinations with repetition, the number of such decompositions is $C_{n + 2 m - 1}^{2 m}$ C_{n+2m-1}^{2m} (see Eolymp problem $11551$ ).

Example

In the first test, there are $5$ valid variants:

$a = [1, 1], b = [2, 2]$ a = [1, 1], b = [2, 2];
$a = [1, 2], b = [2, 2]$ a = [1, 2], b = [2, 2];
$a = [2, 2], b = [2, 2]$ a = [2, 2], b = [2, 2];
$a = [1, 1], b = [2, 1]$ a = [1, 1], b = [2, 1];
$a = [1, 1], b = [1, 1]$ a = [1, 1], b = [1, 1]

The corresponding combined sequence satisfies the inequalities

1 \leq a_{1} \leq a_{2} \leq b_{2} \leq b_{1} \leq 2

1 \le a_1 \le a_2 \le b_2 \le b_1 \le 2

Let us perform a change of variables:

y_{1} = a_{1} - 1, y_{2} = a_{2} - a_{1}, y_{3} = b_{2} - a_{2}, y_{4} = b_{1} - b_{2}, y_{5} = 2 - b_{1}

y_1 = a_1 - 1, \\ y_2 = a_2 - a_1, \\ y_3 = b_2 - a_2, \\ y_4 = b_1 - b_2, \\ y_5 = 2 - b_1

Let us sum the variables:

y_{1} + y_{2} + ... + y_{5} = 1, 0 \leq y_{i} \leq 1

y_1 + y_2 + ... + y_5 = 1, 0 \le y_i \le 1

This equation has $5$ solutions. In each of them, exactly one variable $y_{i}$ y_i equals $1$ , while all the others equal $0$ . Let us consider the correspondence between these solutions and the original sequences:

Algorithm implementation

Declare a constant and an array $d p$ , where $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

#define MOD 1000000007
long long dp[3001][30];

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

long long Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = (Cnk(n - 1, k - 1) + Cnk(n - 1, k)) % MOD;
}

C++

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

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

Initialize the $d p$ array.

memset(dp, -1, sizeof(dp));

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

printf("%d\n", Cnk(n + 2 * m - 1, 2 * m));