1525. Задача группирования

Дано множество из n целых чисел. Вы можете выбрать из этого множества k различных элементов, чтобы сформировать группу. Две группы считаются разными, если существует хотя бы один элемент, который присутствует в одной группе, но отсутствует в другой. Например, если множество состоит из 4 элементов a, b, c, d, и требуется выбрать два элемента, то ab, bc, cd, bd, ad и ac являются всеми корректными и различными группами.

Система группирования называется полной, если для заданного k число различных групп максимально. В этом примере множество {ab, bc, cd, bd, ad, ac} образует полную систему группирования.

Для некоторой полной системы группирования её оценка (fitness) вычисляется следующим образом:

· каждая группа вносит вклад, равный произведению всех чисел в этой группе;

· все вклады групп суммируются;

· итоговая оценка определяется как суммарный вклад , где  — ограничивающий параметр.

В приведённом выше примере, для k = 2, оценка равна

F₂ = (ab + bc + cd + bd + ad + ac) mod m

Если k = 1, то оценка равна

F₁ = (a + b + c + d) mod m

Ваша задача – определить полную систему группирования, которая дает максимально возможную оценку.

Вход. Каждый тест начинается с двух положительных целых чисел n (2 ≤ n ≤ 1000) и m (1 ≤ m < 2³¹). Следующая строка содержит n натуральных чисел, каждое из которых не больше 1000. Последний тест содержит n = m = 0 и не обрабатывается.

Выход. Для каждого теста выведите в отдельной строке максимально возможную оценку для системы группирования.

Пример входа	Пример выхода
4 10 1 2 3 4 4 100 1 2 3 4 4 6 1 2 3 4 0 0	5 50 5

РЕШЕНИЕ

динамическое программирование

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

Пусть а₁, a₂, …, a_n – заданные n чисел. Обозначим через F_ik (i ³ k) сумму всех возможных произведений по k чисел, выбранных среди первых i чисел a₁, …, a_i. Построим следующую таблицу значений F_ik:

Для четырех чисел получаем:

· F_4,1 = a₁ + a₂ + a₃ + a₄;

· F_4,2 = a₁a₂ + a₁a₃ + a₁a₄ + a₂a₃ + a₂a₄ + a₃a₄;

· F_4,3 = a₁a₂a₃ + a₁a₂a₄ + a₁a₃a₄ + a₂a₃a₄;

· F_4,4 = a₁a₂a₃a₄;

Выполняются следующие рекуррентные соотношения:

F_i1 = F_(i-1)1 + a_i,

F_ii = F_{(i-1) (i-1)} * a_i, 1 £ i £ n

F_ik = F_(i-1)k + F_{(i-1) (k-1)} * a_i, 1 £ i £ n, 1 < k < i

Например,

· F_3,2 = F_2,2 + F_2,1 * a₃ = a₁a₂ + (a₁ + a₂) * a₃ = a₁a₂ + a₁a₃ + a₂a₃;

· F_4,3 = F_3,3 + F_3,2 * a₄ = a₁a₂a₃ + (a₁a₂ + a₁a₃ + a₂a₃) * a₄ =

a₁a₂a₃ + a₁a₂a₄ + a₁a₃a₄ + a₂a₃a₄

Значения каждой следующей строки вычисляются на основе значений предыдущей, поэтому для хранения достаточно одного линейного массива d размером до 1000. Пересчёт значений i - ой строки следует выполнять с конца: сначала вычисляется F_ii, затем F_i(i-1) и так далее до F_i1. Все вычисления необходимо проводить по модулю m.

Пример

Рассмотрим первый тест. Построим две таблицы: в первой вычисления выполняются без модуля, а во второй – по модулю m = 10.

Например,

· F_4,2 = F_3,2 + F_3,1 * 4 = 11 + 6 * 4 = 35;

· F_4,3 = F_3,3 + F_3,2 * 4 = 6 + 11 * 4 = 50;

Ответом является максимальное значение в четвёртой строке второй таблицы.

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

Объявим линейный массив d, в котором будут пересчитываться значения F_ik.

long long d[1000];

Вводим количество чисел n и значение m. Для каждого входного теста предварительно обнуляем массив d. Первое число a₁ заносим в 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 £ i < n) и пересчитываем значения F_ik для 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;

}

Находим максимальное значение среди элементов массива d и сохраняем его в переменную res.

res = 0;

for (i = 0; i < n; i++)

if (d[i] > res) res = d[i];

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

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

}