Разбор задачи «Космические телескопы и карта сигналов»

Идея задачи

В задаче есть неизвестный массив a из n чисел. Для некоторых отрезков известно значение побитового OR на этом отрезке. Нужно найти сумму значений XOR по всем непустым подмножествам позиций массива.

На первый взгляд задача кажется сложной: сам массив не дан, отрезков много, а все подмножества позиций перебирать невозможно.

Но у этой задачи есть очень сильное наблюдение: нам вообще не нужно восстанавливать весь массив. Достаточно понять, какие биты могут встречаться хотя бы в одном элементе массива.

Шаг 1. Что на самом деле важно

Обозначим через

A = a_1 OR a_2 OR ... OR a_n

общий побитовый OR всех элементов массива.

Именно это число полностью определяет ответ.

Почему? Потому что сумма XOR по всем подмножествам удобно разбирается по битам.

Если какой-то бит нигде в массиве не встречается, то он никогда не появится и в XOR никакого подмножества.

Если же какой-то бит хотя бы один раз встречается в массиве, то оказывается, что среди всех подмножеств этот бит будет равен 1 ровно в половине случаев.

Значит задача сводится к двум вопросам:

1. Как найти общий OR всех элементов массива?
2. Почему после этого ответ равен A * 2^(n-1)?

Шаг 2. Как найти общий OR массива

По условию для каждого ограничения дано:

a_l OR a_{l+1} OR ... OR a_r = x

Пусть у нас есть много таких значений x. Рассмотрим их общий OR:

X = x_1 OR x_2 OR ... OR x_m

Утверждение:

A = X

Почему это верно

В одну сторону

Если некоторый бит равен 1 в одном из значений x, то на соответствующем отрезке есть хотя бы один элемент массива, у которого этот бит равен 1.

Значит этот бит точно входит и в A.

То есть каждый бит из X обязательно есть в A.

В другую сторону

Если некоторый бит есть в A, значит он есть хотя бы у одного элемента массива.

Но по условию гарантируется, что массив удовлетворяет всем ограничениям, и каждый такой бит должен проявляться в каком-то ограничении на отрезок, содержащий этот элемент. Тогда этот бит встретится хотя бы в одном значении x.

Значит каждый бит из A обязательно есть в X.

Следовательно, A = X.

Итак, чтобы найти общий OR массива, достаточно просто взять OR всех значений x из входных данных.

Шаг 3. Как посчитать сумму XOR по всем подмножествам

Теперь предположим, что общий OR массива равен A.

Нужно найти сумму XOR по всем непустым подмножествам позиций.

Разберём один фиксированный бит с номером k.

Случай 1. Бит k нигде не встречается

Тогда ни в одном XOR этот бит не появится. Его вклад в ответ равен 0.

Случай 2. Бит k встречается хотя бы в одном элементе

Тогда среди всех подмножеств позиций ровно у половины XOR по этому биту будет равен 1.

Почему так?

Выберем любой элемент массива, у которого этот бит равен 1.

Теперь рассмотрим произвольное подмножество позиций:

• если этот элемент в подмножестве отсутствует, добавим его;
• если он присутствует, удалим его.

Такое действие меняет чётность количества выбранных элементов с этим битом, а значит меняет значение XOR по данному биту:

• было 0, станет 1;
• было 1, станет 0.

Получается, все подмножества разбиваются на пары, и в каждой паре ровно у одного подмножества этот бит в XOR равен 1.

Значит среди всех 2^n подмножеств у ровно 2^(n-1) подмножеств этот бит даёт единицу.

Пустое подмножество здесь не мешает: если бит вообще где-то встречается, у пустого множества этот бит равен 0, так что число подмножеств с единицей всё равно равно 2^(n-1) и среди непустых тоже.

Следовательно, вклад бита k в ответ равен:

2^k * 2^(n-1)

Если сложить такие вклады по всем битам, которые входят в A, получим:

answer = A * 2^(n-1)

Итоговая формула

Если обозначить

A = x_1 OR x_2 OR ... OR x_m,

то ответ равен

A * 2^(n-1) mod (10^9 + 7)

Алгоритм

Для каждого набора данных:

1. Считать n и m.
2. Завести переменную all_or = 0.
3. Для каждого ограничения считать l, r, x.
4. Выполнить all_or |= x.
5. Посчитать pow2 = 2^(n-1) mod MOD.
6. Вывести (all_or * pow2) mod MOD.

Почему алгоритм работает

Мы доказали два ключевых факта:

1. Общий OR всех элементов массива равен OR всех чисел x из ограничений.
2. Для каждого бита, присутствующего в этом OR, вклад в сумму XOR по всем непустым подмножествам равен 2^k * 2^(n-1).

Значит итоговая формула корректна, а алгоритм действительно вычисляет правильный ответ.

Оценка сложности

На один набор данных:

• чтение входа и вычисление общего OR: O(m);
• быстрое возведение двойки в степень: O(log n).

Итого:

O(m + log n) на один набор данных.

Это очень быстро и легко проходит при больших ограничениях.

Разбор на примере

Пусть:

• n = 4

• ограничения такие:

  • [1, 2] -> 3
  • [3, 4] -> 1

Тогда:

A = 3 OR 1 = 3

То есть в массиве точно могут встречаться только биты числа 3.

Теперь используем формулу:

answer = 3 * 2^(4-1) = 3 * 8 = 24

Значит ответ равен 24.

Решение на C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

long long mod_pow(long long a, long long e) {
    long long r = 1;
    while (e > 0) {
        if (e & 1) {
            r = (r * a) % MOD;
        }
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;

        long long all_or = 0;

        for (int i = 0; i < m; i++) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            all_or |= x;
        }

        long long ans = all_or % MOD;
        ans = ans * mod_pow(2, n - 1) % MOD;

        cout << ans << '\n';
    }

    return 0;
}

Решение на Python

MOD = 10**9 + 7


def mod_pow(a, e):
    result = 1
    while e > 0:
        if e & 1:
            result = result * a % MOD
        a = a * a % MOD
        e >>= 1
    return result


t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    all_or = 0

    for _ in range(m):
        l, r, x = map(int, input().split())
        all_or |= x

    ans = all_or % MOD
    ans = ans * mod_pow(2, n - 1) % MOD
    print(ans)

Что здесь важно запомнить

У задачи очень характерная идея:

• не нужно восстанавливать массив;
• не нужно отдельно работать с отрезками;
• не нужно считать XOR по подмножествам напрямую.

Нужно заметить две вещи:

1. Все нужные биты собираются простым OR по всем x.
2. Каждый присутствующий бит попадает в XOR ровно у половины всех подмножеств.

Именно такие наблюдения часто превращают сложную на вид задачу в короткое решение на несколько строк.

Короткий вывод

Формула ответа:

(x_1 OR x_2 OR ... OR x_m) * 2^(n-1) mod (10^9 + 7)

Поэтому всё решение сводится к одному проходу по входным данным и быстрому возведению в степень.