Зета-преобразование

Если различаешь свёртку по разбиениям и сумму по покрытиям, листай до «Теперь сам».

Как думаешь, сколько раз нужен один и тот же вклад

Раньше мы перебирали подмаски одной маски. Теперь надо суммировать значения подмасок для всех масок сразу. Вложенные циклы проходят 3ⁿ пар: у каждого элемента три роли - отсутствовать в большом множестве, присутствовать только в большом или присутствовать в обоих. Можно ли использовать общие частичные суммы и не повторять одинаковую работу?

На что это похоже

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

Механизм: по одному разрешённому биту

В начале z[S] = f[S]. При обработке бита b к строке, содержащей b, прибавляем строку без b. После первых i битов в z[S] уже учтены все удаления среди этих битов, а остальные остаются как в S. Это инвариант преобразования. После n проходов разрешены любые удаления, то есть учтены все подмножества.

Обратный шаг вычитает строку без бита. Во время прохода эта строка не меняется, потому что она не содержит обрабатываемый бит. Поэтому каждый проход обратим без вспомогательной копии. Для суммы по целым числам этого достаточно; для произвольных объектов нужны определённые сложение и вычитание.

Свёртка определена как h[S] = Σ f[A]·g[S\A] по A ⊆ S. Она считает разбиения на две непересекающиеся части. Если просто перемножить зета-образы и обратить, получится сумма по A∪B=S, разрешающая пересечения. Чтобы удалить их, положим fᵢ[A]=f[A] только при |A|=i, иначе ноль, и аналогично для g.

После преобразования перемножаем слои: слой k получает сумму произведений слоёв i и k-i. Обращение оставит пары с объединением S. Для k=|S| равенство |A|+|B|=|A∪B| возможно только без пересечения. Поэтому нужный ответ находится именно в этом слое.

Правило

Зета-преобразование суммирует по включению, Мёбиус обращает эти суммы. Свёртка по непересекающимся частям требует слоёв по мощности. Оценки считают арифметические действия; при длинных целых нужно учитывать и их размер.

Разбор: сумма и восстановление

Для двух элементов возьми значения [1,2,3,4] в порядке масок 0,1,2,3. Зета-образ [1,3,4,10]: последняя строка содержит все четыре числа. Обратное преобразование вернёт исходный массив, а не приблизительные значения.

def transform(values, inverse=False):
    z = values[:]
    n = (len(z) - 1).bit_length()
    sign = -1 if inverse else 1
    for b in range(n):
        for mask in range(1 << n):
            if mask & (1 << b):
                z[mask] += sign * z[mask ^ (1 << b)]
    return z


def convolution(f, g):
    size = len(f)
    n = (size - 1).bit_length()
    ranks = [s.bit_count() for s in range(size)]
    fs = [transform([f[s] if ranks[s] == k else 0
                     for s in range(size)])
          for k in range(n + 1)]
    gs = [transform([g[s] if ranks[s] == k else 0
                     for s in range(size)])
          for k in range(n + 1)]
    answer = [0] * size
    for k in range(n + 1):
        layer = [sum(fs[i][s] * gs[k-i][s]
                     for i in range(k + 1)) for s in range(size)]
        layer = transform(layer, inverse=True)
        for s in range(size):
            if ranks[s] == k:
                answer[s] = layer[s]
    return answer


def direct(f, g):
    result = []
    for s in range(len(f)):
        total, a = 0, s
        while True:
            total += f[a] * g[s ^ a]
            if a == 0:
                break
            a = (a - 1) & s
        result.append(total)
    return result


print(transform([1, 2, 3, 4]))
print(transform(transform([1, 2, 3, 4]), inverse=True))
f = [1, 2, 1, 3, 2, 0, 4, 1]
g = [2, 0, 3, 1, 1, 4, 0, 2]
assert convolution(f, g) == direct(f, g)
print("Свёртка:", convolution(f, g))
print("Один элемент:", convolution([0, 1], [0, 1]))

[1, 3, 4, 10]
[1, 2, 3, 4]
Свёртка: [2, 4, 5, 13, 5, 6, 15, 13]
Один элемент: [0, 0]

Программа сравнивает быструю свёртку с прямой на восьми масках. Прямой вариант хранится только как эталон проверки. Образ по мощности требует n+1 массивов, каждый длины 2ⁿ; это O(n·2ⁿ) памяти. Времени больше, чем для одной зеты, из-за перемножения всех пар слоёв.

Разбор: один элемент обнаруживает лишнее пересечение

Пусть f и g ненулевые только на одноэлементном множестве и там равны единице. Нужная свёртка на этом множестве равна нулю: нельзя отдать единственный элемент обеим непересекающимся частям. Простое перемножение зета-образов после обращения даст единицу: это покрытие, в котором элемент взят дважды. Слои по мощности кладут вклад в слой два, а мы берём слой один, поэтому лишний вклад исчезает.

Что ломается без этого

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

Зачем это в работе

Динамика по подмножествам объединяет два независимых решения на непересекающихся наборах, например при подсчёте раскрасок или объединении частей решения. Прямой перебор всех разбиений порождает 3ⁿ; слои позволяют ускорить сразу всю таблицу. Если нужен результат лишь для одной небольшой маски, преобразование всех 2ⁿ строк может быть лишней работой.

Теперь сам

Пусть f и g равны единице на всех подмножествах двухэлементного S. Чему равна h[S]? Сколько пар покрытий получилось бы без запрета пересечений?