Два масиви#11725

Два масиви (Розбір)

Розглянемо об'єднану послідовність:

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

Її довжина дорівнює $2 m$ . З умови задачі випливає, що ця послідовність:

впорядкована в порядку незростання;
складається з чисел від $1$ до $n$ .

Таким чином, задача зводиться до підрахунку кількості незростаючих послідовностей

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

Виконаємо заміну змінних:

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}

Тоді всі $y_{i} \geq 0$ y_i \ge 0, а їхня сума дорівнює

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

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

Отже, задача зводиться до підрахунку способів розкласти число $n - 1$ n - 1 на $2 m + 1$ 2m + 1 невід'ємних цілих доданків. Кожному такому розкладенню відповідає рівно одна незростаюча послідовність $x_{1}, x_{2}, ..., x_{2 m}$ x_1, x_2, ..., x_{2m}, а значить — рівно одна пара масивів $(a; b)$ .

За класичною формулою для комбінацій з повтореннями число таких розкладів дорівнює $C_{n + 2 m - 1}^{2 m}$ C_{n+2m-1}^{2m} (див. задачу Єолімп $11551$ ).

Приклад

У першому тесті існує $5$ підходящих варіантів:

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

Відповідна об'єднана послідовність задовольняє нерівностям

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

Зробимо заміну змінних:

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

Просумуємо змінні:

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

Це рівняння має $5$ рішень. В кожному з них рівно одна змінна $y_{i}$ y_i дорівнює $1$ , а всі інші дорівнюють $0$ . Розглянемо відповідність цих рішень до початкових послідовностей:

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

Оголосимо константу і масив $d p$ , для якого $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

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

Функція Cnk обчислює значення біноміального коефіцієнта $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++

Основна частина програми. Читаємо вхідні дані.

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

Ініціалізуємо масив $d p$ .

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

Обчислюємо і виводимо відповідь $C_{n + 2 m - 1}^{2 m}$ C_{n+2m-1}^{2m}.

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