Битовое сжатие

  • Из-за него в «асимптотиках» появляется /64
  • На Всеросе часто дают задачи, где оно может принести «бесплатные» ~20 баллов
  • bitset есть в stl; говорят, самописный быстрее

Процессор так устроен, что работает сразу с блоками по 32 или 64 бита (зависит от архитектуры, но получить что-то меньше одного байта он в принципе не может). Иными словами, сделать & двух bool-ом и двух long-ов примерно одинаково по скорости.

Часто нам требуется сделать много одинаковых операций над элементами булевого массива. Проксорить два массива, например. Здесь появляется такая идея: сгруппировать элементы массива в блоки по 64 и каждый блок считать двоичным числом. Тогда мы можем ксорить сразу все 64 бита за одну операцию.

Это всё можно кодить и вручную, но в STL это уже сделали до нас, создав структуру, ведущую себя как большое двоичное число со всеми стандартными битовыми операциями — bitset.

Работать с ним нужно вот так:

In [ ]:
const int lim = 1000;
bitset<lim> b; // создать битсет размера lim (должно быть константой)
b.set();       // заполнить единицами
b.reset();     // заполнить нулями
b.flip();      // заменить единички на нули и наоборот
b.count();     // посчитать число единичек
cout << b;     // вывести битовую строку

Также для битсетов работает вся битовая арифметика — &, |, ^, ~, <<, >> и их варианты с [operator]=.

Рюкзак

Задача: даны $n$ предметов с положительными целыми весами $a_i$ и рюкзак размера $lim$, выбрать подмножество предметов с максимальной суммой, не превышающий размер рюкзака.

Обычно его решают так:

In [ ]:
bool dp[lim] = {}; // так можно его заполнить нулями
dp[0] = 1;
for (int i = 0; i < n; i++)
    for (int x = lim - a[i]; x >= 0; x--)
        dp[x + a[i]] |= dp[x];

…а с битсетом оно разгоняется так:

In [ ]:
bitset<lim> b;
b[0] = 1;
for (int i = 0; i < n; i++)
    b |= b << a[i];

Цикл длины 3

Пусть нам нужно узнать, есть ли цикл длины 3 в ориентированном графе из $n$ вершин, заданном своей матрицей смежности. Обернем матрицу в битсет, и тогда задача решается за $O(\frac{n^3}{64})$ следующим образом:

In [ ]:
bitset<maxn> g[maxn]; // матрица смежности
for (int a = 0; a < n; a++) {
    for (int b = 0; b < n; b++) {
        if (g[a][b] && (~g[a] & g[b]).any()) {
            // цикл найден
        }
    }
}

Benchmark: на серверах CodeForces этот код при $n = 5000$ работает за 7 секунд.

Перемножение матриц

Матрица смежности графа, возведенная в степень $n$, имеет комбинаторный смысл: количество способов дойти из $a$ в $b$, используя ровно $n$ переходов. Иногда нам не нужно знать число способов, и нам просто хватит знания, можно ли вообще через $n$ ходов там оказаться. Тогда вместо числового умножения нам хватит битового умножения:

In [ ]:
typedef bitset<maxn> t;
typedef array<t, maxn> matrix;

matrix operator* (matrix a, matrix b) {
    matrix c;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(a[i][j])
                c[i] |= b[j];
    return c;
}

Гаусс

Иногда встречаются задачи, требующие решения системы линейных уравнений. Очень большая часть из них на самом деле над полем $\mathbb{Z}_2$ — то есть все числа по модулю 2. К примеру: есть $n$ переключателей лампочек, каждый активированный переключатель меняет состояние (включает или выключает) какого-то подмножества из $n$ лампочек. Известно состояние всех лампочек, нужно восстановить состояние переключаетелей.

Нас по сути просят решить следующую систему:

$$ \begin{cases} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n \equiv b_1 \pmod 2\\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2n} x_n \equiv b_2 \pmod 2\\ \ldots \\ a_{n1} x_1 + a_{n2} x_2 + \ldots + a_{nn} x_n \equiv b_n \pmod 2 \end{cases} $$

Здесь $x$ — состояния переключателей, $b$ — состояния лампочек, $A$ — информация о том, влияет ли переключатель на лампочку.

В таком случае можно значительно ускорить и упростить обычный метод Гаусса:

In [ ]:
t gauss (matrix a) {
    for (int i = 0; i < n; i++) {
        int nonzero = i;
        for (int j = i+1; j < n; j++)
            if (a[j][i])
                nonzero = j;
        swap(a[nonzero], a[i]);
        for (int j = 0; j < n; j++)
            if (j != i && a[j][i])
                a[j] ^= a[i];
    }
    t x;
    for (int i = 0; i < n; i++)
        x[i] = a[i][n] ^ a[i][i];
    return x;
}

Код находит вектор $x$ из уравнения $Ax = b$ при условии, что решение существует и единственно. Для простоты кода, предполагается, что вектор $b$ приписан справа к матрице $A$.