Обереги тумар


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

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

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

В мастерской в Бишкеке делают тумары — серебряные обереги. На каждом из n оберегов выбит код a[i] — целое число от 0 до 2^B − 1. Мастер собирает цепочку из K оберегов: на каждое из K мест по очереди кладёт любой из n оберегов (копий сколько угодно, так что один оберег может встречаться в цепочке несколько раз). Цепочки различаются, если на каком-то месте лежат обереги с разными номерами.

«Сила» цепочки — побитовое исключающее ИЛИ (XOR) кодов всех её оберегов. Для каждого из q заказов x найдите, сколько существует цепочек с силой x, по модулю 998244353.

Рисунок

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

В первой строке — четыре целых числа B, n, K, q (1 ≤ B ≤ 17, 1 ≤ n ≤ 2 · 10⁵, 1 ≤ K ≤ 10¹⁸, 1 ≤ q ≤ 10⁵). Во второй строке — n чисел a[i] (0 ≤ a[i] < 2^B). В третьей строке — q чисел x (0 ≤ x < 2^B).

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

Для каждого заказа выведите в отдельной строке количество цепочек по модулю 998244353.

Пример 1

Вход:

2 3 2 4
1 2 3
0 1 2 3

Выход:

3
2
2
2

Пояснение

Обереги с кодами 1, 2, 3, цепочки из двух оберегов: всего 9 цепочек. Сила 0 у цепочек (1, 1), (2, 2), (3, 3); сила 1 — у (2, 3) и (3, 2); сила 3 — у (1, 2) и (2, 1).

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

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

Подсказка

Преобразование Адамара (Уолша) превращает XOR-свёртку в поэлементное умножение.


Комментарии

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