Wataru

Посмортите на метод Гаусса. Там получается диагональная матрица путем прибавления одной строки к другим и перестановки строк. Так вот - прибавление одной строки к другой с коэффициентом - это и есть домножение матрицы на трансвекцию.

Единственная проблема - надо переставлять строчки местами. Тут вам поможет класический пазл о помене двух чисел без использования вспомогательных переменных:

a = a + b;
b = a - b;
a = a - b;

Эти три операции поменяют местами a и b. При чем они уже выглядят как трансвекции - только вторая операция не совсем вида a += b*k.

Но можно чуть чуть поменять:

a = a + b;
b = b - a;
a = a + b;

Тут три трансвекции и строки меняются местами, только одна из них домножается на -1. Но это домножение метод гауса нисколько не меняет.

Вот и ваш алгоритм.

Никак. Есть методы получить число, которое будет стоять на заданной позиции (или числа на отрезке) в отсортированном массиве быстрее сортировки (алгоритм QuickSelect). Как-то быстрее сортировки найти все числа на нечетных позициях - нельзя.

Edit: Если стандартная сортировка не работает и L большое, то стоит посмотреть в сторону radix sort. Если бы L было относительно небольшим - то лучший вариант был бы сортировка подсчетом.

Вам нужно сделать побитовое И с маской, где стоят 0 в нужных вам разрядах (и 1 в остальных). Маску можно задавать прямо бинарной или шестнадцатеричной константой.

Тут нет никакого готового алгоритма. Это геометрическая задача раскроя. Надо порисовать и придумать какой-то паттерн. Рассмотреть несколько случаев и выбрать наилучший в зависимости от ваших размеров.

В комментариях уже упомянули алгоритм Нарайаны. Он работает с повторяющимеся элементами. Надо найти самый правый элемент строго больший предыдущего, поменять предыдущий с минимальным строго больше его правее и отсортировать массив правее этой позиции (можно перевернуть его).

Тут же можно за один проход по магазинам. Сначала пройдитесь по вашим комбинациям и сложите слова в хешмап "слово" -> список номеров пар, в которых оно есть.

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

Если же вы можете один раз что-то предподсчитать для всех магазинов, то потом можно выполнять "запросы" даже не проходясь по всем магазинам.

Можно по каждому тегу составить список магазинов, имеющих его в названии, упорядоченный как-то (допустим, по id магазинов). Эту структуру можно построить за один проход по всем магазинам и сохранить.

Затем ваш запрос на пар тегов можно обрабатывать объеденяя и пересекая упорядоченные списки. Эти операции, как в сортировке слиянием, делаются за один проход по списку.

В хужшем случае, где используется очень частый тег, обработка запроса будет почти как полный просмотр всех магазинов (даже если в ответ попадет их малая часть), но в среднем этот метод будет работать неплохо.

Самое эффективное - использовать какой-нибудь SSE (гуглите shift bits sse. Лучше всего, мне кажется, подойдет _mm_slli_epi64). Но там очень много кода и случаев будет. Придется отдельно разбирать случаи сдвига влево и вправо, отдельно вычленять биты, которые SSE операция при сдвиге бы потеряла и записывать куда надо.

Следующий по эффективности вариант - это читать в int64_t, и там сдвигать биты. Придется сначала из переменной доставать старшые/младшие 1-7 бит и писать их отдельно, потом сдвигать биты и записывать куда надо. Используйте memcopy для чтения/записи 64-ех бит. Еще можно ускорить, если отдельно обработать первые несколько байт до 64-битного выравнивания, и потом придется еще обрабоать отдельно лишние 0-7 байтов в конце, если их количество не делится на 8.