Сегодня речь пойдет об использовании массива двоичных цифр в качестве структуры для хранения данных. Прежде чем приступить к решению новой задачи, расскажу, для чего это может пригодиться.
Замена boolean
Двоичные цифры можно использовать в качестве замены переменной типа boolean, если нужно сохранить много таких значений такого типа и при этом сэкономить память. Двоичная цифра может принимать всего два значения: 0 и 1, что соответствует true и false. Самая простая реализация такого массива — сумма степеней двойки. Например, двоичное число 1111 можно представить в виде числа 1 + 2 + 4 + 8 = 15. Если необходимо добавить в такой «массив» значение с номером i, считая справа, достаточно прибавить 2 в степени i, если это значение необходимо удалить, это можно сделать путем вычитания из суммы числа 2 в степени i.
Экономия памяти заметна, если значений становится много. Например, для 64 значений типа boolean в C++ потребуется 64 байт памяти, а для 64-значного двоичного числа — всего 64 бит = 8 байт. Получаем экономию в 8 раз. Перейдем к задаче.
Задача
Для последовательности из N натуральных чисел (все числа в последовательности различны, каждое число не превосходит 10000) определить количество пар (порядок элементов в паре не имеет значения), в которых сумма элементов делится на m = 87, при этом элемент с бОльшим индексом должен быть больше элемента с меньшим индексом.
Однозначность представления элементов
По условию задачи все элементы различны, значит, если представить каждый элемент в виде m*k+r, 0 ≤ r < m, m, k, r — целые неотрицательные, то k и r для каждого числа будут уникальными. Этим мы и воспользуемся для хранения чисел.
Представим себе некоторую таблицу с 10000/m = 115 строками (округлил вверх, так как после 114*m еще есть числа, не превосходящие 10000) и m = 87 столбцами. Каждое число последовательности можно записать в эту таблицу так: поставить крестик (галочку, точку) в ячейку в строке с номером k и столбце с номером r (все обозначения такие же, как в абзаце ранее). И никогда в одной клетке не «столкнутся» два элемента последовательности, так как все элементы различны. Эту таблицу будем использовать для проверки пар чисел.
Проверяем пары
Если некоторое число x стоит в строке нашей таблицы под номером k и в столбце под номером r, то с ним в пару можно поставить те числа, которые имеют парный остаток pr = (m — r) % m, то есть находятся в столбце с номером pr. Второе условие (элемент с бОльшим индексом больше) проверим так: для текущего числа x будем брать только те числа, которые меньше него, то есть в таблице расположены выше (клетки выделены), в сроках с номерами от 0 до k — 1 включительно.
Важно заметить, что если число x имеет остаток, который больше своего парного, то число, имеющее такое же значение k (находится в нашей таблице в одной с x строке) так же подойдет под второе условие. Это тоже придется учитывать при определении количества подходящих пар.
Запоминаем таблицу
Для хранения всей таблицы при любом значении N понадобится, очевидно, округлить_вверх(10000/m)*m переменных или элементов массива. В C++, например, это займет округлить_вверх(10000/m)*m = 10005 байт (при использовании типа boolean), что существенно больше критерия эффективной по памяти программы (используемая память — до 4 килобайт). Здесь на помощь придут массивы двоичных цифр, то есть числа, образованные сложением степеней двойки, о которых я говорил в самом начале. Далее приведу реализацию на двух языках: Python и C++.
Python
Этот язык программирования очень хорошо может работать с большими числами. Создадим массив numbers на m элементов типа int, в каждый элемент будем помещать один столбец таблицы. При обработке числа найдем значения k = x // m, r = x % m и pr = (m — r) % m. Пусть p = 2 в степени k, gp — степень двойки, такая, что числа, у которых степень двойки равна или больше нее, в пару не подойдут. Очевидно, что gp = p, если r ≤ pr и gp = p * 2 в противном случае. Возьмем остаток от деления числа numbers[r] на gp и посчитаем количество значащих единиц в двоичной записи такого числа (описано далее). Это количество и будет количеством элементов, которые можно поставить в пару с элементом x. Добавим его к общему количеству, как в идее 3 «Два массива».
C++
В этом языке программирования самый большой по размеру тип данных — тип unsigned long long int (используем unsigned, потому что все числа в задаче положительные). В unsigned long long int «помещается» максимально 2^64 — 1, что с точки зрения записи двоичных цифр соответствует 64 единицам. Зная, что 10000/m приблизительно равно 115, приходим к выводу, что потребуется 2 переменных указанного выше типа. Создадим двумерный массив numbers[m][2]. Пусть в numbers[r][0] будет левая половина бит (биты 127-64 при счете справа налево), а в numbers[r][1] — правая (биты 63-0), так проще работать.
Вся логика считывания количества и записи числа аналогична логике на Python, за исключением следующего: при 0 ≤ k ≤ 63 работаем только с правой половиной, так же, как на Python; при k ≥ 64 будем обрабатывать так: посчитаем все значащие единицы в правой половине и посчитаем так же, как на Python, единицы в левой половине, уменьшив для этого k на 64.
Подсчет числа единиц в двоичной записи
На сайте geeksforgeeks.org я нашёл способ быстро это сделать. Вручную посчитаем число единиц в записи первых 16 чисел, от 0 до 15:
Для более крупных чисел будем считать единицы рекурсивно, каждый раз «откусывая» от числа 4 знака справа и запуская функцию подсчета от оставшейся части числа.
Итоги
Предложенное решение эффективно по времени, так как по последовательности проходим всего 1 раз, все подсчеты числа единиц не зависят от N. Программа эффективна по памяти, так как занимает в памяти около 1,5 килобайт < 4 килобайт, и занимаемая память не растет с ростом N.
Код задачи на Python: https://github.com/kormanowsky/ege-27/blob/master/4_powers_of_two.py
Код задачи на C++: https://github.com/kormanowsky/ege-27/blob/master/4_powers_of_two.cpp
