Наборы специй для плова


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Повар из Узгена готовит плов и хранит n баночек со смесями специй. Каждая смесь задана битовой маской a[i] из B бит: бит j равен 1, если в смеси есть специя номер j (зира, барбарис, кориандр, …).

Если высыпать в казан несколько смесей, в плове окажутся только те специи, которые есть во всех выбранных смесях (так уж устроены узгенские специи), то есть результат — побитовое И (AND) масок.

Рисунок

Для каждого из q вопросов x найдите, сколько существует непустых наборов баночек, побитовое И масок которых равно ровно x. Наборы различаются номерами баночек. Ответы выведите по модулю 10⁹ + 7.

Входные данные

В первой строке — B, n, q (1 ≤ B ≤ 20, 1 ≤ n ≤ 10⁶, 1 ≤ q ≤ 10⁵). Во второй строке — n чисел a[i] (0 ≤ a[i] < 2^B). В третьей — q чисел x (0 ≤ x < 2^B).

Выходные данные

Для каждого вопроса выведите количество наборов по модулю 10⁹ + 7.

Пример 1

Вход:

3 3 4
3 5 7
1 7 0 3

Выход:

2
1
0
2

Пояснение

Маски 3 (011), 5 (101), 7 (111). И равно 1 у наборов {3, 5} и {3, 5, 7}; равно 7 — только у набора {7}; равно 0 — ни у одного.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 15.

Подсказка

Посчитайте для каждой маски m число g[m] баночек, содержащих все специи из m (сумма по надмножествам). Тогда наборов с И, содержащим m, ровно 2^g[m] − 1, а дальше помогает формула включений-исключений по надмножествам.


Комментарии

Еще нет ни одного комментария.