DP по подмножествам со счётом перестановок — задача «Axis Walking» РАЗБОР

Bitmask DP — техника, у которой пугающий ярлык: $n$ до 24, состояние «подмножество», экспоненциальное по подмножествам. На самом деле это та же динамика, что и линейная — только индекс состояния пробегает не отрезок $[0, n]$, а множество всех $2^n$ подмножеств. Когда из условия ясно, что порядок прохождения элементов важен, а сами элементы — фиксированный набор без повторений, и $n$ маленькое (до 22–24) — bitmask DP часто оказывается единственным разумным способом.

Эта задача — эталонный учебный кейс: ответ — число перестановок с ограничением «не попадать в запрещённые точки», и эти запреты завязаны на сумму уже сделанных шагов. То есть состояние полностью описывается набором уже сделанных шагов, без необходимости знать их порядок — потому что сумма коммутативна. Ровно та структура, на которую ложится bitmask DP с состоянием «маска использованных».

---

Что дано

Игрок ходит по числовой прямой. Перед игрой ему даны $n$ положительных целых чисел $a_1, \ldots, a_n$ — длины шагов. За один ход игрок выбирает один ещё не использованный шаг и сдвигается на эту длину вправо. Каждый шаг используется ровно один раз; всего ходов — ровно $n$.

Перед игрой на прямой отмечены $k$ «плохих» точек $b_1, \ldots, b_k$. После каждого хода игрок не должен оказаться ни в одной из плохих точек. Стартует игрок в точке $0$, эта стартовая точка тоже не должна быть плохой (если $0 \in \{b_j\}$, ответ — $0$).

Нужно найти количество различных порядков использования шагов $a_1, \ldots, a_n$, при которых это условие выполняется. Ответ берётся по модулю $10^9 + 7$.

Ограничения

• $1 \le n \le 24$.
• $0 \le k \le 2$.
• $1 \le a_i \le 10^9$.
• $0 \le b_j \le 10^{15}$.

Формат ввода

n
a_1 a_2 ... a_n
k
b_1 b_2 ... b_k

Формат вывода

Одно целое число — количество допустимых перестановок $a_1, \ldots, a_n$ по модулю $10^9 + 7$.

Пример A

3
2 3 5
2
5 7

Перебор всех $3! = 6$ перестановок:

Ответ — $1$.

Пример B

4
1 2 3 4
2
3 7

Из 24 перестановок проходят 8 (полный список — в разделе «Проверка на примерах»). Ответ — $8$.

---

Идея решения

Когда из условия в принципе непонятно, как атаковать, помогает упражнение «зафиксируй, какую информацию реально требует ограничение». Здесь ограничение работает после каждого хода: «текущая координата не равна ни одному из $b_j$». Текущая координата — это сумма уже сделанных шагов; она зависит только от множества уже использованных индексов, не от их порядка.

Это и есть ключевое наблюдение. Если у нас две частичные перестановки, использующие один и тот же набор индексов (например, $\{a_1, a_3\}$ против $\{a_3, a_1\}$), они приведут игрока в одну и ту же точку. Поэтому достаточно знать подмножество использованных индексов — а не конкретный порядок их использования.

Состояние DP: $dp[mask]$ = число способов прийти в текущую конфигурацию, то есть число различных порядков, в которых можно использовать индексы из $mask$ как первые $|mask|$ шагов так, чтобы все частичные суммы по пути были «хорошими» (не попадали в $\{b_j\}$).

Сразу две приятные особенности:

1. Состояние одномерное. Маска — это число от $0$ до $2^n - 1$; никакого дополнительного параметра состояния (как «последний использованный элемент» в других bitmask-задачах) здесь не нужно.
2. Сумма по маске — функция от маски. Точка, в которой стоит игрок после использования индексов $mask$, равна $S[mask] = \sum_{i \in mask} a_i$. Эту сумму можно посчитать заранее за $O(2^n)$ — независимо от dp.

---

Состояние и переход

Состояние. $dp[mask]$ — число различных порядков уложить элементы $mask$ как первые $|mask|$ ходов так, чтобы все промежуточные суммы (после 1-го, 2-го, …, $|mask|$-го хода) не лежали в $\{b_j\}$.

База. $dp[\emptyset] = dp[0] = 1$ — единственный способ ничего не сделать. Стартовая точка $0$ предполагается «хорошей» — отдельная проверка перед запуском DP покрывает случай $0 \in \{b_j\}$.

Переход. Зафиксируем маску $mask \neq \emptyset$. Если $S[mask] \in \{b_j\}$, то после прохода через $mask$ игрок попадёт в «плохую» точку — таких порядков нет, $dp[mask] = 0$.

Иначе посмотрим, какой элемент пришёл последним в текущей перестановке. Это какой-то $i \in mask$. После его удаления из маски остаётся подмножество $mask \setminus \{i\}$ — предыдущая конфигурация. Перебираем все $i \in mask$ как «последний» и суммируем:

$$dp[mask] = \sum_{i \in mask} dp[mask \setminus \{i\}].$$

Идея перехода — перебор по последнему действию. Это стандартный приём для bitmask DP в задачах, где порядок важен.

Ответ. $dp[(2^n - 1)]$ — все $n$ элементов использованы, все промежуточные суммы хорошие.

Почему «по последнему действию», а не «по первому»

Можно было бы определить переход через первое действие: $dp'[mask] = \sum_{i \in mask} dp'[mask \setminus \{i\}]$, что выглядит так же. Но смысл состояния тогда другой: $dp'[mask]$ — число способов разместить $mask$ как последние $|mask|$ ходов. Тогда фильтр по сумме должен проверять не только текущий префикс, но и «сумму до прихода в текущее множество», то есть полную сумму массива минус $S[mask]$ — это менее естественно. Перебор по последнему действию — более прямой.

---

Предподсчёт сумм по маскам

Считать $S[mask]$ в момент перехода — означает проход по $|mask|$ битам, итого $O(2^n \cdot n)$ только на суммы. Это удвоит и так тесную сложность.

Лучше — рекуррент по младшему биту. Пусть $low(mask) = mask\ \&\ (-mask)$ — младший установленный бит (например, $low(0b1010) = 0b0010$). Пусть $i = \log_2 low(mask)$ — позиция этого бита. Тогда

$$S[mask] = S[mask \oplus low(mask)] + a_i.$$

Это даёт $S$ за $O(2^n)$ — один проход по маскам в порядке возрастания, $O(1)$ на маску. Аналогично можно перебирать по старшему биту — выбор не влияет на корректность.

---

Руками на примере B

Возьмём пример: $n = 4$, $a = [1, 2, 3, 4]$, $bad = \{3, 7\}$.

Шаг 1. Считаем $S[mask]$ для всех 16 масок. Обозначаю битами «использовал ли элемент $a_i$» — бит $0$ соответствует $a_1 = 1$, бит $1$ соответствует $a_2 = 2$ и т.д. Маска $0b1011 = 11$ означает «использованы $a_1, a_2, a_4$».

Шаг 2. Считаем $dp[mask]$ в порядке возрастания $mask$ (это автоматически гарантирует, что все подмаски уже посчитаны).

Ответ — $dp[15] = 8$. Совпадает с прямым подсчётом 8 валидных перестановок из 24 (полный список в разделе «Проверка на примерах»).

Обратите внимание на «занулённые» маски $3, 4, 11, 12$: они участвуют в переходах дальше, но всегда вносят 0. Это правильно: если на пути в любую конфигурацию мы попадём в «плохую» сумму — этот порядок отбраковывается, что и делает занулённый член.

---

Алгоритм целиком

прочитать n, a[1..n], k, bad[1..k]
если 0 ∈ bad:
    вывести 0; выйти

MOD ← 10^9 + 7
size ← 2^n
S[0]   ← 0
для mask от 1 до size - 1:
    low ← mask & -mask
    i   ← log2(low)
    S[mask] ← S[mask ⊕ low] + a[i]

dp[0]  ← 1
для mask от 1 до size - 1:
    если S[mask] ∈ bad:
        dp[mask] ← 0
        продолжить
    cur ← 0
    m ← mask
    пока m ≠ 0:
        low ← m & -m
        cur ← cur + dp[mask ⊕ low]
        m ← m ⊕ low
    dp[mask] ← cur mod MOD

вывести dp[size - 1]

Циклы по mask и по битам внутри mask — самая горячая часть. На $n = 24$: внешний цикл — $2^{24} \approx 1.6 \cdot 10^7$ итераций, внутренний — в среднем $n / 2 = 12$. Итого порядка $2 \cdot 10^8$ операций тела цикла. В C++ это 2–3 секунды на современном CF-сервере, в Python — десятки секунд, не помещается в TL без перехода на нативные расширения.

---

Код решения

Сразу важное замечание про языки: эта задача в Python почти не проходит даже с агрессивными оптимизациями. Чистый Python на $n = 24$ занимает $\sim 30$–$60$ секунд, что превышает типичный CF TL ($2$–$3$ секунды). Python-версия ниже корректна и проходит локальные тесты до $n = 20$ за секунду; для CF-сабмита нужен C++. Включаю обе версии для целей разбора — Python читается легче и помогает разобраться в идее.

Комментарии по реализации

• Тип для сумм. $a_i$ до $10^9$, $n$ до $24$ — сумма до $2.4 \cdot 10^{10}$. В C++ long long обязателен; int переполнится. В Python целые числа произвольной точности.
• Тип для dp. Значения по модулю $10^9 + 7$ — помещаются в int (32 бита). В C++ важно делать cur отдельно как long long, потому что $n$ слагаемых по $10^9$ дают сумму до $2.4 \cdot 10^{10}$ до взятия модуля. Если хранить cur как int, на $n = 24$ переполнение случится примерно на середине внутреннего цикла.
• Память на $n = 24$. В C++: S — $16M \cdot 8 = 128$ МБ, dp — $16M \cdot 4 = 64$ МБ. Итого $\sim 192$ МБ. CF обычно даёт $256$ МБ — впритык, но проходит. В Python list of int — $\sim 28$ байт на элемент, итого $\sim 900$ МБ; не помещается. Если упирается — array.array('q', ...) сокращает до 8 байт.
• Извлечение младшего бита. mask & -mask работает в обоих языках. В C++ позиция бита — через __builtin_ctz за $O(1)$; в Python — (low).bit_length() - 1, тоже $O(1)$ для интов в нужном диапазоне.
• Цикл по битам через m &= m - 1. Это идиома «снять младший установленный бит». В C++ компактнее, чем XOR через low. В Python обе идиомы дают одинаковую производительность.
• Множество bad в Python. При $k \le 2$ выбор между set и list не критичен (проверка членства за $O(k)$ против $O(1)$ — на 2 элементах разница нулевая). Я оставил set для общности; для $k$ большего масштаба разница будет.

---

Проверка на примерах

Пример A

$n = 3$, $a = [2, 3, 5]$, $bad = \{5, 7\}$.

Ответ — $dp[7] = 1$. ✓

Пример B

Полный список 8 валидных перестановок (для контроля):

Все 8 перестановок свободны от значений 3 и 7 во всех префиксах. Прямой подсчёт совпал с DP: $dp[15] = 8$. ✓

---

Крайние случаи

• $k = 0$ (нет плохих точек). Все $n!$ перестановок проходят. DP вернёт $n! \bmod (10^9 + 7)$. На $n = 24$: $24! \bmod (10^9 + 7)$ — корректно за $O(2^n \cdot n)$, шаблон не упрощается, но и не ломается.
• $0 \in bad$. Стартовая точка — плохая, ответ $0$. Эту проверку нужно делать до DP, потому что в самом DP мы не проверяем «до первого хода»: dp[0] = 1 без учёта bad. Без явной проверки шаблон вернёт неправильный $n!$ вместо $0$.
• $\sum a_i \in bad$. Финальная точка плохая, ответ $0$. DP это поймает сам: $S[(2^n - 1)] = \sum a_i$ попадает в bad, ветка «продолжить» обнулит $dp[(2^n - 1)]$.
• Все маски «плохие». Например, $n = 1$, $a = [5]$, $bad = \{5\}$. Ответ $0$ — единственная маска $\{1\}$ имеет сумму 5, попадает в bad.
• $n = 1$, $bad = \emptyset$. Ответ $1$ — единственная перестановка из одного шага.
• Очень близкие к лимиту $b_j$. $b_j$ до $10^{15}$, $S[mask]$ до $24 \cdot 10^9 \approx 2.4 \cdot 10^{10}$. Все «плохие» значения, бо́льшие $\sum a_i$, никогда не достигаются — формально DP их игнорирует, корректно. В коде сравнение S[mask] == bad[j] работает на одинаковом 64-битном типе, переполнения нет.

---

Типичные ошибки

1. Забытая проверка $0 \in bad$. Без неё dp[0] = 1 без условий, и шаблон вернёт неверный $n!$ вместо $0$ для случая «старт уже плохой».
2. cur как int в C++. На $n = 24$ сумма $n$ значений $\le 10^9 - 1$ до взятия модуля переполнит int. Накапливать обязательно в long long.
3. Использование int для $S[mask]$ в C++. Сумма до $2.4 \cdot 10^{10}$, переполнение int гарантировано. long long для $S$.
4. Перестановка не в той форме. Естественный неверный вариант: $dp[mask][i] =$ «маска и последний элемент». Это даёт правильный ответ, но память $O(2^n \cdot n)$ — на $n = 24$ это $\sim 400$ МБ, не помещается. Корректный шаблон обходится без i, потому что сумма по маске не зависит от порядка — нет смысла раздваивать состояние.
5. Проверка bad через линейный поиск по большому $k$. В этой задаче $k \le 2$, и линейная проверка for (int j = 0; j < k; ++j) — даже быстрее, чем unordered_set. В похожих задачах с большим $k$ нужен set / unordered_set или предварительная сортировка с бинпоиском.
6. Итерация по маскам в неправильном порядке. Возрастающий порядок $mask$ гарантирует, что все подмаски (с меньшим числом битов и меньшим значением) уже посчитаны. Идти, например, по числу установленных битов и внутри — по значению — тоже корректно, но это лишняя сложность реализации; обычный for mask in 1..size-1 достаточен.
7. Переполнение при $S[mask] \in bad$ для огромных $b_j$. Если хранить $b_j$ в int, сравнение S[mask] == bad[j] при $b_j > 2^{31}$ даст неопределённое поведение из-за неявных приведений. long long везде убирает риск.
8. «Оптимизация» с пропуском занулённых масок. Желание не считать $dp[mask]$ для «плохих» масок отдельным шагом — корректное, но удалять их из массива нельзя: они нужны как нули в переходах для бо́льших масок (см. пример B, маски 3, 4, 11, 12 нужны для переходов в 7, 13, 14, 15).

---

Сложность

• Время. Внешний цикл по маскам — $2^n$. Внутренний цикл по битам в маске — в худшем случае $n$, в среднем $n/2$. Сумма по всем маскам числа установленных битов — $\sum_{mask} \text{popcount}(mask) = n \cdot 2^{n-1}$. Итого $O(n \cdot 2^{n-1}) = O(n \cdot 2^n)$. На $n = 24$: $\sim 2 \cdot 10^8$ — в C++ 2–3 секунды.
• Память. $O(2^n)$ для массива $S$ и $O(2^n)$ для $dp$. На $n = 24$ — $\sim 192$ МБ в C++, не помещается в Python без array.array.
• Предподсчёт сумм. $O(2^n)$ — линейно по числу масок, по $O(1)$ операций каждая.

Альтернативное состояние $dp[mask][i]$ (последний элемент) при той же асимптотике даёт $O(n \cdot 2^n)$ времени, но $O(n \cdot 2^n)$ памяти. На $n = 24$ это уже не проходит по памяти. Поэтому для задач, где порядок внутри маски не важен для перехода, версия с одномерным состоянием — единственная разумная.

---

Связанные задачи

• Гамильтонов путь / цикл за $O(n^2 \cdot 2^n)$. Здесь состояние двумерное — $dp[mask][last]$. «Последний» нужен, потому что переход — это «добавить ребро last → next», и стоимость зависит от пары вершин. На $n \le 18$ — терпимо ($\sim 10^7$).
• DP по подмножествам подмножества (subset sum DP). $dp[mask] = \min(\text{ans}(mask \setminus sub) + f(sub))$, где sub пробегает все подмаски mask. Тонкость — порядок перебора подмасок: sub = (sub - 1) & mask — стандартная идиома, даёт суммарную сложность $O(3^n)$.
• DP по битовой маске с дополнительным числовым параметром. Когда состояние требует «маска + значение в каком-то диапазоне» — это смесь двух парадигм; на полосе CF 2300+.
• Counting/permutations через включения-исключения. Альтернатива bitmask DP для задач со счётом перестановок с ограничениями. Часто даёт лучший асимптотически результат — $O(\text{poly}(n))$ против $O(2^n \cdot n)$ — но требует более тонкого формулирования.
• Тема в этой серии. Bitmask DP — часть третьей ступени серии «Стратегия победы: DP — от очевидного шаблона к ёмкому состоянию»: переход к подмножеству-состоянию — содержательный шаг от линейного DP и от двумерного DP.

---

Итого

• Идея: $dp[mask]$ — число допустимых порядков пройти через подмножество $mask$ как первые $|mask|$ шагов. Сумма по маске = координата игрока после $|mask|$ ходов.
• Ключевое наблюдение: сумма $\sum_{i \in mask} a_i$ не зависит от порядка → второй параметр состояния не нужен.
• Переход: перебор «последнего» использованного элемента — $dp[mask] = \sum_{i \in mask} dp[mask \setminus \{i\}]$ при $S[mask] \notin bad$, иначе $0$.
• Предподсчёт сумм: $S[mask] = S[mask \oplus \text{low}(mask)] + a_{\log_2 \text{low}(mask)}$ за $O(2^n)$.
• Сложность: $O(n \cdot 2^n)$ времени, $O(2^n)$ памяти. На $n = 24$ — 2–3 секунды в C++.
• Главные ловушки: проверка $0 \in bad$ до DP, long long для сумм и cur, не раздваивать состояние по «последнему элементу» (лишняя память).

Источник задачи: Codeforces 327E «Axis Walking».