Разбор задачи «Лунные раскопки»

Идея задачи

Дан массив a длины n. Для каждого непрерывного отрезка [l, r] нужно вычислить его ценность:

\[ (a_l \oplus a_{l+1} \oplus \dots \oplus a_r) \cdot (r - l + 1) \]

где ⊕ — побитовое XOR.

Нужно найти сумму таких значений по всем отрезкам массива по модулю 998244353.

Если пытаться перебрать все отрезки напрямую, получится слишком медленно: отрезков O(n^2), а внутри каждого ещё нужно как-то считать XOR и длину. Даже если XOR на отрезке получать быстро, полный перебор всех пар l, r всё равно не подойдёт при больших ограничениях.

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

Шаг 1. Префиксные XOR

В задачах на XOR очень часто помогает массив префиксных XOR.

Обозначим:

\[ p_0 = 0, \] \[ p_i = a_1 \oplus a_2 \oplus \dots \oplus a_i. \]

Тогда XOR на отрезке [l, r] равен:

\[ a_l \oplus a_{l+1} \oplus \dots \oplus a_r = p_r \oplus p_{l-1}. \]

Это стандартное и очень важное свойство: XOR на отрезке выражается через два префикса.

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

\[ (p_r \oplus p_{l-1}) \cdot (r - l + 1). \]

Уже лучше, но пока всё ещё непонятно, как суммировать это быстро по всем l и r.

Шаг 2. Разделим задачу по битам

Число удобно рассматривать по отдельным битам.

Если в каком-то числе установлен бит b, то его вклад в значение числа равен 2^b.

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

Пусть мы зафиксировали некоторый бит b. Нужно понять, у каких отрезков XOR на этом бите равен 1.

Для отрезка [l, r] этот бит в

\[ p_r \oplus p_{l-1} \]

равен 1 тогда и только тогда, когда b-й бит у p_r и p_{l-1} различается.

То есть:

• если у p_r на этом бите 0, то нужен такой p_{l-1}, у которого там 1;
• если у p_r на этом бите 1, то нужен такой p_{l-1}, у которого там 0.

Именно такие пары префиксов образуют отрезки, где бит b входит в XOR.

Шаг 3. Что нужно посчитать для фиксированного правого конца

Пусть правый конец отрезка фиксирован: r.

Тогда нужно рассмотреть все j = l - 1, где 0 <= j < r. Отрезок [l, r] имеет длину:

\[ r - l + 1 = r - j. \]

Если для текущего r мы знаем все подходящие j, у которых нужный бит префикса противоположен текущему, то вклад этого бита в ответ равен:

\[ \sum (r - j) \cdot 2^b. \]

Здесь сумма берётся по всем подходящим j.

Раскроем скобки:

\[ \sum (r - j) = (\text{число таких } j) \cdot r - \sum j. \]

Получается, для каждого значения бита 0 и 1 нам достаточно хранить:

• сколько уже было префиксов с таким значением бита;
• сумму их позиций.

Это и даёт быстрое решение.

Шаг 4. Какие данные будем поддерживать

Для каждого бита отдельно будем идти слева направо по массиву и поддерживать:

• cnt[0] — сколько уже встречено префиксов, у которых текущий бит равен 0;
• cnt[1] — сколько уже встречено префиксов, у которых текущий бит равен 1;
• sum_pos[0] — сумма позиций этих префиксов;
• sum_pos[1] — сумма позиций этих префиксов.

Пусть после обработки элемента с индексом i текущий префиксный XOR по этому биту равен pref.

Тогда нужны все старые префиксы с битом pref ^ 1. Обозначим это значение как need.

Тогда суммарный вклад длин всех подходящих отрезков, заканчивающихся в позиции i, равен:

\[ cnt[need] \cdot (i + 1) - sum_pos[need]. \]

Почему здесь (i + 1), а не i?

Потому что очень удобно хранить позицию префикса p_i как число i в 1-базной логике или как i + 1 в 0-базной реализации. Это стандартный приём: текущий правый конец массива имеет длины отрезков, которые естественно выражаются через такие позиции.

Главное — делать это последовательно во всей формуле.

Шаг 5. Почему изначально cnt[0] = 1

До начала массива уже существует префикс p_0 = 0.

Это очень важно. Именно он позволяет корректно учитывать отрезки, начинающиеся с первого элемента.

Поэтому перед началом прохода по массиву нужно записать, что один префикс с нулевым значением уже есть.

То есть:

• cnt[0] = 1
• cnt[1] = 0
• sum_pos[0] = 0
• sum_pos[1] = 0

Небольшой пример

Рассмотрим массив:

1 3 2

Префиксные XOR:

• p[0] = 0
• p[1] = 1
• p[2] = 1 xor 3 = 2
• p[3] = 2 xor 2 = 0

То есть:

0, 1, 2, 0

Дальше можно разбирать биты по отдельности. Например, для младшего бита получится, что часть отрезков даёт единицу в XOR, а часть нет. Аналогично для второго бита. Складывая их вклады с весами 1, 2, 4, ..., мы получаем итоговую сумму.

Вручную для всех отрезков:

• [1,1]: 1 * 1 = 1
• [2,2]: 3 * 1 = 3
• [3,3]: 2 * 1 = 2
• [1,2]: (1 xor 3) * 2 = 2 * 2 = 4
• [2,3]: (3 xor 2) * 2 = 1 * 2 = 2
• [1,3]: (1 xor 3 xor 2) * 3 = 0 * 3 = 0

Сумма равна 12.

Пошаговый алгоритм

1. Считываем массив.
2. Перебираем все биты от 0 до 29.

3. Для каждого бита отдельно:

   • обнуляем текущий префикс pref;
   • заводим массивы cnt и sum_pos;
   • кладём туда начальный префикс 0;
   • идём по массиву слева направо;
   • обновляем текущий бит префиксного XOR;
   • находим, сколько подходящих старых префиксов дают единицу в этом бите;
   • добавляем их вклад в ответ для этого бита;
   • после этого добавляем текущий префикс в структуры.
4. Умножаем вклад бита на 2^bit.
5. Складываем всё по модулю 998244353.

Почему решение работает быстро

Битов всего 30, потому что значения массива меньше 2^30.

Для каждого бита мы делаем один проход по массиву.

Итоговая сложность:

• по времени: O(30 * n)
• по памяти: O(1), если не считать сам массив

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

Типичные ошибки

1. Забыть про префикс p_0 = 0

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

2. Перепутать позиции префиксов

Нужно аккуратно выбрать одну систему:

• либо хранить индексы как 0, 1, 2, ...,
• либо использовать в формуле i + 1.

Обе версии работают, если делать всё последовательно.

3. Обновлять cnt и sum_pos слишком рано

Сначала нужно посчитать вклад текущей позиции, используя только предыдущие префиксы, и только потом добавить текущий префикс в структуры.

4. Не брать модуль

Суммы очень большие, поэтому нужно регулярно брать остаток по модулю 998244353.

Эталонное решение на C++

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

const int MOD = 998244353;

int addmod(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    if (a < 0) a += MOD;
    return a;
}

int mulmod(long long a, long long b) {
    return int((a * b) % MOD);
}

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

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int answer = 0;

    for (int bit = 0; bit < 30; bit++) {
        int pref = 0;
        int cur = 0;

        vector<int> cnt(2, 0);
        vector<int> sum_pos(2, 0);

        cnt[0] = 1;

        for (int i = 0; i < n; i++) {
            pref ^= ((a[i] >> bit) & 1);

            int need = pref ^ 1;

            int total_right = mulmod(cnt[need], i + 1);
            int contribution = addmod(total_right, -sum_pos[need]);
            cur = addmod(cur, contribution);

            cnt[pref]++;
            if (cnt[pref] >= MOD) cnt[pref] -= MOD;

            sum_pos[pref] = addmod(sum_pos[pref], i + 1);
        }

        answer = addmod(answer, mulmod(1 << bit, cur));
    }

    cout << answer << '\n';
    return 0;
}

Разбор кода на C++

Внешний цикл идёт по битам:

for (int bit = 0; bit < 30; bit++)

Для каждого бита поддерживаем только нули и единицы, поэтому массивы размера 2:

vector<int> cnt(2, 0);
vector<int> sum_pos(2, 0);

Начальный префикс 0 уже существует:

cnt[0] = 1;

После чтения очередного элемента обновляем текущий бит префиксного XOR:

pref ^= ((a[i] >> bit) & 1);

Теперь нам нужны все старые префиксы с противоположным значением бита:

int need = pref ^ 1;

Их общий вклад по длинам:

int total_right = mulmod(cnt[need], i + 1);
int contribution = addmod(total_right, -sum_pos[need]);

После этого текущий префикс нужно занести в структуры:

cnt[pref]++;
sum_pos[pref] = addmod(sum_pos[pref], i + 1);

Эталонное решение на Python

import sys

MOD = 998244353


def solve():
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))

    answer = 0

    for bit in range(30):
        pref = 0
        cur = 0

        cnt = [1, 0]
        sum_pos = [0, 0]

        for i in range(n):
            pref ^= (a[i] >> bit) & 1

            need = pref ^ 1

            contribution = (cnt[need] * (i + 1) - sum_pos[need]) % MOD
            cur = (cur + contribution) % MOD

            cnt[pref] += 1
            sum_pos[pref] = (sum_pos[pref] + (i + 1)) % MOD

        answer = (answer + (1 << bit) * cur) % MOD

    print(answer)


if __name__ == "__main__":
    solve()

Разбор кода на Python

Логика полностью совпадает с решением на C++.

Для каждого бита:

• pref хранит текущий префиксный XOR по этому биту;
• cnt[0] и cnt[1] — сколько уже было префиксов каждого типа;
• sum_pos[0] и sum_pos[1] — суммы их позиций.

Вклад текущей позиции считается строкой:

contribution = (cnt[need] * (i + 1) - sum_pos[need]) % MOD

Это и есть сумма длин всех отрезков, заканчивающихся в i, у которых текущий бит XOR равен 1.

После этого текущий префикс добавляется в статистику.

Что полезно вынести из этой задачи

Эта задача хорошо показывает сразу несколько важных идей:

• XOR на отрезке удобно считать через префиксные XOR;
• сложные суммы по всем отрезкам часто можно разложить по битам;
• если в формуле встречается сумма вида r - j, то полезно хранить не только количество объектов, но и сумму их позиций;
• иногда задача на первый взгляд выглядит как O(n^2), но после правильного преобразования решается почти за линейное время.

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

Итог

Мы заменили XOR на отрезке через два префикса, затем разделили задачу по битам и для каждого бита научились быстро считать суммарный вклад всех подходящих отрезков.

Именно это позволило перейти от полного перебора отрезков к решению за O(30 * n).

Это и есть ключевая идея всей задачи.