Информатика → Областная → 2018
Это обсуждение публикации https://olympiads.bc-pf.org/informatics/oblast/2018
Это обсуждение публикации https://olympiads.bc-pf.org/informatics/oblast/2018
У Алана есть 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.
Если не поймешь что делать дальше напиши.
Почему ссылка ведет меня в мой профиль? (Или это закрытая группа?)
1 лайк
Да, закрытая группа
Извиняюсь тупанул, и случайно округлил вниз там, в целом идея та же остается целых чисел на отрезке от минимальной суммы до максимальной суммы будет примерно O(n)
Я пользовался этим фактом, но ловил TL, возможно косяк в моем объединений двух частей массива(при дележки MITM’ом), не знаю 
Ну там значение i-го элемента меняется меньше чем на 1 всегда, а значит максимум изменение суммы это O(n)
Скинь код, я думаю у тебя проблема в даблах