Область 2018 2 тур | Задача С

У Алана есть n башен, у каждой из которых есть параметр a[i] - числитель рук и параметр b[i] - знаменатель рук. В q очень легких делах, которых он задумал, ему нужно определить руки у башен. Для этого, каждой башне он может сказать сделать целое количество рук - |a[i] / b[i]| (округление вниз) или дробное количество рук - a[i] / b[i]. Для i-го дела, которые он задумал, Алану необходимо суммарно ровно x[i] рук. Для каждого из этих дел Алан берет все n башен, то есть суммарная рукость всех башен должна равняться x[i]. Помогите Алану найти количество способов сделать это, для каждого из q легких дел.

Мысли по задаче: На 51 балл написал перебор масок, после попытался использовать MITM, надеясь на то, что количество целых рук мало(это оказалось не так).

Помогите с решением этой задачи на 100

1 лайк

N <= 40
q <= 1e5
x[i] <= 4e6
a[i] <= 1e5
b[i] <= 1e5

Условие задачи:
\sum\limits^{i \leq n}_{i=1} ruk_i = x, ruk_i может быть равно [\frac{a_i}{b_i}] или \lfloor\frac{a_i}{b_i}\rfloor. Нужно посчитать количество способов получит x.

Дополнительная деталь для решения, все x которые не лежат на отрезке [\sum\limits^{i \leq n}_{i=1} \lfloor\frac{a_i}{b_i}\rfloor; \sum\limits^{i \leq n}_{i=1} [\frac{a_i}{b_i}]] имеют ответ 0, Кол-во целых значений на этом отрезке это примерно n.

Если не поймешь что делать дальше напиши.

Почему ссылка ведет меня в мой профиль? (Или это закрытая группа?)

Да, закрытая группа

Извиняюсь тупанул, и случайно округлил вниз там, в целом идея та же остается целых чисел на отрезке от минимальной суммы до максимальной суммы будет примерно O(n)

Я пользовался этим фактом, но ловил TL, возможно косяк в моем объединений двух частей массива(при дележки MITM’ом), не знаю :frowning:

Ну там значение i-го элемента меняется меньше чем на 1 всегда, а значит максимум изменение суммы это O(n)

Скинь код, я думаю у тебя проблема в даблах