Подарок к покупке
Магазин проводит акцию: покупатель выбирает один товар и один подарок, и комплект должен стоить ровно s тенге — ни тенге больше, ни меньше. Маркетологи перебирают разные суммы s и для каждой хотят знать, сколькими способами можно собрать комплект. Товаров и подарков много, вопросов тоже.
Способы различаются, если различается товар или подарок, даже когда цены у них одинаковые.
Вход
В первой строке три числа n, m, q (1 ≤ n, m, q ≤ 10⁵) — число товаров, подарков и вопросов. Во второй строке n цен товаров, в третьей — m цен подарков; все цены — целые от 1 до 10⁵. Дальше q строк по одному числу s (0 ≤ s ≤ 2 · 10⁵).
Выход
Для каждого вопроса — число пар «товар, подарок» с суммой цен ровно s.
Примеры
Пример 1
4 3 5 1500 2000 2000 3500 500 1000 1500 3000 3500 2500 100 5000
3 2 3 0 1
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перебор пар — 10¹⁰ операций. Перебор различных цен товаров для каждого вопроса — столько же в худшем случае. Можно ли ответить на все возможные s сразу?
2Подсказка 2
Пусть A(x) = Σ (число товаров по цене p) · xp и B(x) — то же для подарков. Что стоит при xs в произведении A(x) · B(x)?
3Идея
Коэффициент при xs в A · B — это сумма произведений ap · bs−p по всем p, то есть ровно число пар с суммой s. Значит, ответы на все вопросы — коэффициенты произведения двух многочленов степени до 10⁵, и его считает быстрое преобразование Фурье за O(C log C), где C — наибольшая цена.
4Разбор
Строим массивы счётчиков a и b длины 10⁵ + 1, дополняем нулями до степени двойки не меньше 2 · 10⁵ + 1 — иначе круговая свёртка завернёт большие суммы в маленькие, — делаем два прямых преобразования, перемножаем поточечно, обратное преобразование и округление до ближайшего целого. В Python это пять строк с numpy.fft.rfft и irfft; numpy.convolve не подходит — он сворачивает в лоб, за квадрат.
В решении на Go одно преобразование вместо двух: товары кладём в действительную часть, подарки — в мнимую. Квадрат числа a + ib равен a² − b² + 2iab, и мнимая часть квадрата многочлена, делённая на два, — как раз свёртка a и b.
Точность: ответ доходит до 10¹⁰ (третий тест — сто тысяч одинаковых товаров и сто тысяч одинаковых подарков), а ошибка округления в БПФ такой длины на много порядков меньше 0,5, так что округление восстанавливает целое точно.
4+Решение
5Сложность
Свёртка — O(C log C) при C = 2¹⁸, ответ на вопрос — O(1). Итого O(n + m + q + C log C).
6Типичные ошибки
- Цикл по ценам на каждый вопрос. Верно, но O(q · D) при D различных цен — до 10¹⁰ шагов; четвёртый тест его не пропускает.
- Круговая свёртка без дополнения нулями. Сумма 150 000 при длине 2¹⁷ = 131 072 «завернётся» и прибавится к сумме 18 928.
- 32-битный ответ. 10¹⁰ не помещается в int32.
- Отбрасывание дробной части вместо округления. 2,9999999 после обратного БПФ — это 3, а не 2.