Количество уникальных элементов множества

[Dmitriy40]

Конечно хотелось бы не $O(\prod_p |B_p|)$, а $O(|A_p|)$, что очень сильно меньше.
Например, для $p=31$ первое больше второго всего в 1.43 раза, для $p=37$ уже в 2.4 раза, для $p=41$ в 5.1 раза. $|A_{43}|$ мне неизвестно, но оцениваю в 340млн, что в 11 раз меньше общего количества вариантов 3.8млрд. И это плохо, так как тогда $|A_{47}|$ будет порядка 3e9 и в память точно не влезет, а $|A_{59}|$ порядка 3e11 не влезет и на диск.

mihaild в сообщении #1638402 писал(а):

Еще кстати получается, что $A_0$ симметрично с $B_i$. Что это может дать...

Ну, вообще-то $A_0$ это просто все единицы в числе (ну или все нули если & заменить на | и маски $B_i$ тоже инвертировать). Симметрия позволяет считать вдвое меньше, наверное. Но по моему только по одному любому $B_i$ (вот нет бы по каждому).

mihaild в сообщении #1638402 писал(а):

Ну понятно что можно попробовать найти такой набор индексов, что $\left| \mathop{\&}\limits_{i \in S} B_i\right| \ll \prod\limits_{i \in S} |B_i|$. Но не очень понятно, как это делать.

Для малых $i$ (подразумеваю не номер шага, а простое число соответствующее шагу, до 40) можно и полным перебором, но фактически это и делается, только сразу над $A$. А вот дальше, для $i>40$, маски почти перестают перекрываться (в каждой всего 2-3 нулевых бита из 128 и вероятность их совмещения мала).
В принципе вроде можно построить список всех вариантов когда совмещаются нули в масках для больших $i$, быстрее полного перебора, наверное порядка $(b-a+3)!\sum |B_{a\ldots b}|$ вместо $\prod |B_{a\ldots b}|$: после двух масок останется список длиной не произведением их размеров, а примерно утроенного количества любой из (для каждой первой маски из множества вторых подходят лишь 2-3), в остальных нули не совместятся, и уже на этот более короткий список натравливать следующую маску. Только а смысл? Ведь это лишь часть полного списка, остальной же тоже надо обрабатывать.

-- 07.05.2024, 20:49 --

mihaild в сообщении #1638402 писал(а):

даже вопрос о принадлежности нуля итоговому множеству NP-труден.

Это в общем случае, у нас же маски $B_i$ сильно специфичны (например начиная с некоторого $i$ в них нули появляются на всех позициях) и появление нуля гарантировано, априори не очень понятно на какой итерации (хотя Yadryara обосновал прекрасную оценку, хоть и завышенную).

-- 07.05.2024, 20:55 --

В общем я так понял или сугубо вероятностные методы (типа HyperLogLog или CVM, про них ещё подумаю), или хотелки зарезать, ограничиться разумным размером, сделать битовый массив двойного-тройного размера (для уменьшения вероятности коллизий) и просто выставлять в нём бит при появлении элемента с заданным хешем. Как коэффициент заполнения приблизится к половине - вот дотуда и можно будет посчитать. Получится оценка снизу (из-за коллизий хеш-функции), но вроде неплохая. Уж на биты памяти точно хватит если в будущем её (или диска) хватит на 16-32 байтовые элементы.

[Yadryara]

Dmitriy40 в сообщении #1638407 писал(а):

хотя Yadryara обосновал прекрасную оценку, хоть и завышенную

Впс несколько оценок делал. О какой из них речь?

[Dmitriy40]

(Оффтоп)

Yadryara в сообщении #1638446 писал(а):

Dmitriy40 в сообщении #1638407 писал(а):

хотя Yadryara обосновал прекрасную оценку, хоть и завышенную

Впс несколько оценок делал. О какой из них речь?

Конкретно тут я подразумевал что Ваши формулы для окейных строк в обязательном порядке уменьшают vcmin на 1 на каждом шаге (делают ненулевым следующий слева элемент vc[]) и потому за конечное количество шагов сделают ненулевым самый левый элемент vc[0] - как раз число 0 (количество загрязнённости) из утверждения выше.
Завышенной потому что почти во всех случаях уже первая же окейная строка содержит ненулевой vc[0] (из проверенных мною паттернов кроме 3-72), а многие паттерны дают ненулевой vc[0] и ещё раньше.

ToALL: Не обращайте внимания на терминологию, она из той темы для большей понятности коллеге, к этой теме мой ответ не относится, потому кстати и в офтопе.

[Dmitriy40]

Dmitriy40 в сообщении #1638407 писал(а):

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

Не удержался и сделал этот вариант, с дополнительной оценкой границы сверху (все коллизии хеш-функции считать различными числами). Использовал простую хеш-функцию $h(x)=x \bmod p$ с большим простым числом $p$ (порядка 8млрд).
Из известного
$|A_{37}|=2780150:6635520$ - второе число здесь и далее это $\prod\limits_{p=2\ldots i} |B_p|$
получил следующие оценки:
$|A_{41}|= 31047901\ldots66723600:159252480$ - при точном значении $31139242$ для контроля
$|A_{43}|= 221370582\ldots1601366398:3822059520$ - думаю 220млн достаточно близко к точному значению (вместо 340млн по грубой прикидке)
$|A_{47}|= 1162157030\ldots44838259196:107017666560$ - а тут погрешность явно сильно выше (надо или увеличивать хеш-таблицу или улучшать хеш-функцию), но и такая нижняя граница полезна - в память точно уже не влезет

[Dmitriy40]

Усложнив и ускорив хеш-функцию смог посчитать и ещё значение:
$|A_{53}|=3945719926\ldots1524500812796:3638600663040$ - тут погрешность уже как бы не в разы
Скорость составила 160млн/с операций (вычисления элемента, хеш-функции, обращения к 2ГБ битовой таблице, подсчёт коллизий), как-то на удивление много.

Ну собственно можно считать ответ я получил - имеющимся подходом желаемое не реализуемо. А уж насколько именно оно нереально - дело десятое.