11725. Два массива

Даны два числа n и m. Найдите количество таких пар массивов (a, b), что:

· оба массива имеют длину m;

· каждый элемент каждого массива – целое число от 1 до n включительно;

· a_i ≤ b_i для любого индекса i от 1 до m;

· массив a отсортирован в порядке неубывания;

· массив b отсортирован в порядке невозрастания.

Так как ответ может быть слишком большим, вычислите его по модулю 10⁹ + 7.

Вход. Два натуральных числа n и m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10).

Выход. Выведите одно число – количество массивов a и b, удовлетворяющих описанным выше условиям. Ответ выведите по модулю 10⁹ + 7.

Пример входа 1	Пример выхода 1
2 2	5
Пример входа 2	Пример выхода 2
723 9	157557417

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Рассмотрим следующую последовательность: a₁, a₂, …, a_m, b_m, b_m-1, …, b₁. Ее длина равна 2m, она отсортирована в порядке неубывания, каждый ее элемент находится на отрезке от 1 до n. Вычислим количество таких последовательностей.

Данную последовательность можно представить в виде:

1 ≤ x₁ ≤ x₂ ≤ … ≤ x_2m ≤ n

Сделаем замену переменных. Пусть

y₁ = x₁ – 1, y₂ = x₂ – x₁, y₃ = x₃ – x₂, …, y_2m = x_2m – x_2m-1, y_2m+1 = n – x_2m

Теперь каждое y_i ≥ 0, а сумма этих переменных равна n – 1:

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

Теперь задача состоит в том, чтобы разбить целое число n – 1 на 2m + 1 слагаемых, которые могут принимать целые неотрицательные значения. Каждое такое разбиение соответствует одной неубывающей последовательности x₁, x₂, …, x_2m.

Количество таких разбиений равно (смотри задачу Еолимп 11551).

Пример

В первом тесте существуют 5 подходящих вариантов:

· 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]

Рассмотрим последовательность: 1 ≤ a₁ ≤ a₂ ≤ b₂ ≤ b₁ ≤ 2.

Сделаем замену переменных:

y₁ = a₁ – 1, y₂ = a₂ – a₁, y₃ = b₂ – a₂, y₄ = b₁ – b₂, y₅ = 2 – b₁

Просуммируем переменные:

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

Это уравнение имеет 5 решений. В каждом решении одно из значений y_i принимает значение 1, а остальные 0. Рассмотрим соответствия решений уравнения исходным последовательностям:

Реализация алгоритма

Объявим константу и массив dp, для которого dp[n][k] = .

#define MOD 1000000007

long long dp[3001][30];

Функция Cnk вычисляет значение биномиального коэффициента .

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;

}

Основная часть программы. Читаем входные данные.

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

Инициализируем массив dp.

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

Вычисляем и выводим ответ .

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