11725. Two arrays

You are given two numbers n and m. Find the number of pairs of arrays (a, b) such that:

· both arrays have a length of m;

· each element of both arrays is an integer from 1 to n inclusive;

· a_i ≤ b_i for every index i from 1 to m;

· array a is sorted in non-decreasing order;

· array b is sorted in non-increasing order.

Since the result may be too large, compute it modulo 10⁹ + 7.

Input. Two positive integers n and m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10).

Output. Print a single number – the number of arrays a and b that satisfy the conditions described above. Print the result modulo 10⁹ + 7.

Sample input 1	Sample output 1
2 2	5
Sample input 2	Sample output 2
723 9	157557417

SOLUTION

combinatorics

Algorithm analysis

Let us consider the combined sequence:

a₁, a₂, …, a_m, b_m, b_m-1, …, b₁

Its length is 2m. 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 ≤ x₁ ≤ x₂ ≤ … ≤ x_2m ≤ n

Let us perform a change of variables:

y₁ = x₁ – 1,

y₂ = x₂ – x₁,

y₃ = x₃ – x₂,

…,

y_2m = x_2m – x_2m-1,

y_2m+1 = n – x_2m

Then all y_i ≥ 0, and their sum is

y₁ + y₂ + … + y_2m + y_2m+1 = n – 1

Therefore, the problem reduces to counting the number of ways to decompose the number n – 1 into 2m + 1 non-negative integers. Each such decomposition corresponds to exactly one nondecreasing sequence x₁, x₂, …, 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 (see Eolymp problem 11551).

Example

In the first test, there are 5 valid variants:

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

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

· a = [2, 2], b = [2, 2];

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

· a = [1, 1], b = [1, 1]

The corresponding combined sequence satisfies the inequalities

1 ≤ a₁ ≤ a₂ ≤ b₂ ≤ b₁ ≤ 2

Let us perform a change of variables:

y₁ = a₁ – 1,

y₂ = a₂ – a₁,

y₃ = b₂ – a₂,

y₄ = b₁ – b₂,

y₅ = 2 – b₁

Let us sum the variables:

y₁ + y₂ + … + y₅ = 1, y_i ≥ 0

This equation has 5 solutions. In each of them, exactly one variable 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 dp, where dp[n][k] = .

#define MOD 1000000007

long long dp[3001][30];

The Cnk function computes the value of the binomial coefficient .

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;

}

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

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

Initialize the dp array.

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

Compute and print the answer .

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