Сумма побитового ИЛИ элемента max и min каждого подмножества данного массива

Question

Для данного массива я должен найти сумму всех побитовых ИЛИ максимума и минимального элемента из всех возможных подмножеств данного массива, размер которых больше или равен 2. Например: [1,3,5] Подмножество с размером> = 2 является {1,3} {1,5} {3,5} {1,3,5}

{1,3} -библиотечного ИЛИ элемента max и minв этом подмножестве = 3

{1,5} -библиотечный ИЛИ элемента max и min в этом подмножестве = 5

{3,5} -байтный ИЛИ элемента max и minв этом подмножестве = 7

{1,3,5} -биз ИЛИ элемента max и min в этом подмножестве = 5

Таким образом, общая сумма составляет 3 + 5 + 7 + 5 =20.

Я пытался внести изменения с суммой побитового ИЛИ всех возможных подмножеств данного набора, но не смог нарисовать логику.

Примечание: размер массива порядка 10 ^5.

Answer 1

Псевдокод с учетом того, что все числа идут от 1 до 1000:

int count[1001];
int accumulated[1001];

for each element in array:
    count[element]++;

diff_nums = []

for i = 1 to 1000:
    accumulated[i] = accumulated[i - 1] + count[i];
    if (count[i] > 0):
        diff_nums.push(i);

result = 0;

for i = 0 to diff_nums.size():
    i_el = diff_nums[i]
    result += i * (2^(count[i_el]) - count[i_el] - 1)         
    for j = i + 1 to diff_nums.size():
        j_el = diff_nums[j]
        numbers_between_i_and_j = accumulated[j_el - 1] - accumulated[i_el]
        amount_of_subsets_between_i_and_j = 2^(numbers_between_i_and_j)
        amount_of_subsets_with_at_least_1_i = (2^count[i_el] - 1)
        amount_of_subsets_with_at_least_1_j = (2^count[j_el] - 1)

        result += (i_el OR j_el) * amount_of_subsets_between_i_and_j * amount_of_subsets_with_at_least_1_i * amount_of_subsets_with_at_least_1_j

Если D количество уникальных чисел в N, сложность этого:

O (D ^ 2 logn) при условии, что мы делаем log n возведение в степень по модулю

Answer 2

Сортировка массива.Цикл, хотя все пары элементов из набора.Любое подмножество, которое имеет эти элементы как min и max, даст одинаковый вклад.Номер такого подмножества может быть рассчитан по индексу элементов, так как массив отсортирован.Затем вы можете рассчитать объединенный вклад этих подмножеств как побитовое ИЛИ умноженное на число подмножеств.