Задача групування#1525

Задача групування (Розбір)

Нехай $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n — задані $n$ чисел. Позначимо через $F_{ik} (i \geq k)$ F_{ik}~(i \ge k) суму всіх можливих добутків по $k$ чисел, вибраних серед перших $i$ чисел $a_{1}, ..., a_{i}$ a_1, ..., a_i. Побудуємо наступну таблицю значень $F_{ik}$ F_{ik}:

Для чотирьох чисел отримуємо:

$F_{4, 1} = a_{1} + a_{2} + a_{3} + a_{4}$ F_{4,1} = a_1 + a_2 + a_3 + a_4;
$F_{4, 2} = a_{1} a_{2} + a_{1} a_{3} + a_{1} a_{4} + a_{2} a_{3} + a_{2} a_{4} + a_{3} a_{4}$ F_{4,2} = a_1a_2 + a_1a_3 + a_1a_4 + a_2a_3 + a_2a_4 + a_3a_4;
$F_{4, 3} = a_{1} a_{2} a_{3} + a_{1} a_{2} a_{4} + a_{1} a_{3} a_{4} + a_{2} a_{3} a_{4}$ F_{4,3} = a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4 + a_2a_3a_4;
$F_{4, 4} = a_{1} a_{2} a_{3} a_{4}$ F_{4,4} = a_1a_2a_3a_4;

Виконуються наступні рекурентні співвідношення:

F_{i 1} = F_{(i - 1) 1} + a_{i} F_{ii} = F_{(i - 1) (i - 1)} \cdot a_{i}, 1 \leq i \leq n F_{ik} = F_{(i - 1) k} + F_{(i - 1) (k - 1)} \cdot a_{i}, 1 \leq i \leq n, 1 < k < i

F_{i1} = F_{(i-1)1} + a_i\\ F_{ii} = F_{(i-1) (i-1)} \cdot a_i, 1 \le i \le n \\ F_{ik} = F_{(i-1)k} + F_{(i-1) (k-1)} \cdot a_i, 1 \le i \le n, 1 < k < i

Наприклад,

$F_{3, 2} = F_{2, 2} + F_{2,} 1 \cdot a_{3} = a_{1} a_{2} + (a_{1} + a_{2}) \cdot a_{3} = a_{1} a_{2} + a_{1} a_{3} + a_{2} a_{3}$ F_{3,2} = F_{2,2} + F_{2,}1 \cdot a_3 = a_1a_2 + (a_1 + a_2) \cdot a_3 = a_1a_2 + a_1a_3 + a_2a_3;
$F_{4, 3} = F_{3, 3} + F_{3, 2} \cdot a_{4} = a_{1} a_{2} a_{3} + (a_{1} a_{2} + a_{1} a_{3} + a_{2} a_{3}) \cdot a_{4} =$ F_{4,3} = F_{3,3} + F_{3,2} \cdot a_4 = a_1a_2a_3 + (a_1a_2 + a_1a_3 + a_2a_3) \cdot a_4 =
$a_{1} a_{2} a_{3} + a_{1} a_{2} a_{4} + a_{1} a_{3} a_{4} + a_{2} a_{3} a_{4}$
a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4 + a_2a_3a_4

Значення кожного наступного рядка обчислюються на основі значень попереднього, тому для збереження достатньо одного лінійного масиву $d$ розміром до $1000$ . Перерахунок значень $i$ -го рядка слід виконувати з кінця: спочатку обчислюється $F_{ii}$ F_{ii}, потім $F_{i (i - 1)}$ F_{i(i-1)} і так далі до $F_{i 1}$ F_{i1}. Усі обчислення необхідно проводити за модулем $m$ .

Приклад

Розглянемо перший тест. Побудуємо дві таблиці: в першій обчислення виконуються без модуля, а в другій — за модулем $m = 10$ m = 10.

Наприклад,

$F_{4, 2} = F_{3, 2} + F_{3, 1} \cdot 4 = 11 + 6 \cdot 4 = 35$ F_{4,2} = F_{3,2} + F_{3,1} \cdot 4 = 11 + 6 \cdot 4 = 35;
$F_{4, 3} = F_{3, 3} + F_{3, 2} \cdot 4 = 6 + 11 \cdot 4 = 50$ F_{4,3} = F_{3,3} + F_{3,2} \cdot 4 = 6 + 11 \cdot 4 = 50;

Відповіддю є максимальне значення в четвертому рядку другої таблиці.

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

Оголосимо лінійний масив $d$ , у якому будуть перераховуватися значення $F_{ik}$ F_{ik}.

long long d[1000];

Вводимо кількість чисел $n$ та значення $m$ . Для кожного вхідного тесту попередньо обнуляємо масив $d$ . Перше число $a_{1}$ a_1 заносимо в $d [0]$ .

while (scanf("%lld %lld",&n,&m), n + m > 0)
{
  memset(d,0,sizeof(d));
  scanf("%lld",&d[0]);

Далі вводимо значення $x = a_{i + 1} (1 \leq i < n)$ x = a_{i+1}~(1 \le i < n) і перераховуємо значення $F_{ik}$ F_{ik} для $k = i, i - 1, ..., 1$ k = i, i - 1, ..., 1 за наведеними вище рекурентними формулами. Усі обчислення виконуються за модулем $m$ .

  for (i = 1; i < n; i++)
  {
    scanf("%lld",&x);
    d[i] = (d[i-1] * x) % m; 

    for (j = i - 1; j > 0; j--)
      d[j] = (d[j-1] * x + d[j]) % m;

    d[0] = (d[0] + x) % m;
  }

C++

Знаходимо максимальне значення серед елементів масиву $d$ і зберігаємо його у змінній $r es$ .

  res = 0;
  for (i = 0; i < n; i++)	   
    if (d[i] > res) res = d[i];

Виводимо результат.

  printf("%lld\n",res);
}