EZ
А не, хуйня
Size: a a a
2021 May 11
EZ
Не то сказал
CD
Да. Изначально решаю следующую задачу (кажется, эквивалентно). Дан массив чисел, в котором два числа не имеют пары. Найти эти числа, онлайн, один проход.
EZ
Не имеют пары значит встречаются 1 раз?
CD
Есть понятное решение, мы каждое число расширяем в k раз, а именно приписываем каждому числу его само, если k-ый бит 0, и нули иначе
EZ
А что значит онлайн?
EZ
В данном случае
CD
Значит, у тебя один проход по массиву и всё. Дают по числу, пока не запрос ответа
CD
Это, собственно, даёт N ~ k^2 в постановке про вектора
EZ
А если просто посчитать 64 ксора -- 1 для каждого бита
EZ
Ну или в более общем случае -- N штук
CD
Ну это про k^2 решения, я одно такое вроде расписал
CD
64 ксора чисел, у который i-ый бит 0
EZ
Почему это k^2?
CD
ну потому что для i64 ты 64*64 битов используешь
EZ
Понял тебя
CD
а интуитивно среди четверок векторов (Z/2Z)^N должно быть выбираемо 2^(N/4) удовлетворяющих условию
CD
то есть должно существовать решение не сильно больше 4 * 64 бита