Ctrl K

Перекладывание битов ради квадратов

Сложная
Дан массив натуральных чисел values и число pick. С массивом можно сколько угодно раз делать такую операцию: выбрать две разные позиции i и j и одновременно заменить values[i] на values[i] AND values[j], а values[j] — на values[i] OR values[j] (побитовые И и ИЛИ). После всех операций вы выбираете из массива pick элементов и считаете сумму их квадратов. Верните наибольшую возможную сумму по модулю 10⁹ + 7.
Пример 1
values=[5, 5, 2], pick=2 → 74

Берём элементы с индексами 1 и 2: 5 AND 2 = 0, 5 OR 2 = 7. Массив становится [5, 0, 7], выбираем 7 и 5: 49 + 25 = 74.

Пример 2
values=[9, 6], pick=2 → 225

После одной операции получаем [0, 15]. Квадраты: 0 + 225 = 225 — больше, чем 81 + 36 = 117 без операций.

Пример 3
values=[3, 4, 1], pick=1 → 49
Ограничения
  • 1 ≤ pick ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКомпании по четыре в кинозале СредняяСамый узкий отрезок для всех списков СложнаяТройки с нулевым AND СложнаяЦепочки с квадратными суммами СложнаяСлова для головоломок Сложная
загружаем Python…
Вход
values=[5, 5, 2], pick=2
Ожидается
74

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 91 тест на сервере, включая скрытые.