İki massiv#11725

İki massiv (Həll təhlili)

Birləşdirilmiş ardıcıllığı nəzərdən keçirək:

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

Onun uzunluğu $2 m$ -ə bərabərdir. Məsələnin şərtindən aydın olur ki, bu ardıcıllıq:

artmayan sıralama qaydasında;
$1$ -dən $n$ -ə qədər olan ədədlərdən ibarətdir.

Deməli, məsələ aşağıdakı artmayan ardıcıllıqların sayını hesablamağa çevrilir:

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

Değişkenlərin dəyişməsini həyata keçirək:

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}

O zaman bütün $y_{i} \geq 0$ y_i \ge 0, və onların cəmi aydın olur ki

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

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

Beləliklə, bu problem $n - 1$ n - 1 ədədini $2 m + 1$ 2m + 1 qeyri-mənfi tam əlavələrə bölmənin sayını hesaplamaya çevrilir. Belə bölmələrdən hər birinə dəqiq bir artmayan ardıcıllıq $x_{1}, x_{2}, ..., x_{2 m}$ x_1, x_2, ..., x_{2m} uyğun gəlir, buna görə də dəqiq bir cüt array $(a; b)$ uyğun gəlir.

Təkrarlı birləşmələrin klassik formuluna görə belə bölmələrin sayı $C_{n + 2 m - 1}^{2 m}$ C_{n+2m-1}^{2m}-ə bərabərdir (bax Eolimp məsələsi $11551$ ).

Misal

Birinci testdə $5$ uyğun variant var:

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

Uyğun birləşdirilmiş ardıcıllıq aşağıdakı bərabərsizliyin şərtlərini ödəmiş olur:

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

Değişkenlərin dəyişməsini həyata keçirək:

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

Değmək dəyişənləri cəmləyək:

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

Bu bərabərliyin $5$ həlli var. Onlardan hər birində dəqiq bir dəyişən $y_{i}$ y_i-ə $1$ -ə bərabərdir, digər bütün dəyişənlər $0$ -a bərabərdir. Bu həllərin ilkin ardıcıllıqlara uyğun nəticələrini nəzərdən keçirək:

Alqoritmin reallaşdırması

$d p$ dəyişəninin bir dəyişənini və massivi təyin edək, burada $d p [n] [k] = C_{n}^{k}$ dp[n][k] = C_n^k.

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

Cnk funksiyası binomial koeffisienti olan $C_{n}^{k}$ C_n^k-nin qiymətini hesablamaq üçün istifadə edilir.

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++

Proqramın əsas hissəsi. Verilənləri oxuyuruq.

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

Müxtəlif $d p$ -ni başlandığımız.

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

Cavab $C_{n + 2 m - 1}^{2 m}$ C_{n+2m-1}^{2m}-nin hesablayıb və çıxarırıq.

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