B. Easy
Вам дается два целых числа N и R. Посчитайте количество последовательностей, А0, А1, ...,АN-1 таких,
что каждое Ai является целое число, удовлетворяющее 0 <= Аi <= R и А0 + А1 + ... + АN-1 = А0 | А1, ... | АN-
1. '|' Символ обозначает побитовый операнд ИЛИ. Найдите количество таких последовательностей
по модулю 1000000009.
Формат входных данных
Первая строка содержит два числа N и R. 2 <= N <= 10,
1 <= R <= 150000
Формат выходных данных
Первая и единственная строка должна содержать N чисел, ответ на задачу.
easy.in
1. 2 2
2. 2 3
easy.out
1. 7
2. 9
А может R^n?
Так как R небольшое можно перебрать все числа от 0 до R, и для каждого этого числа прибавить к ответу N^количество единичных бит в числе, как то так.UPD неверный алгоритм
Во-первых, не перебрать, если вы говорите о 15000010 - это явный ТЛ.
Ой, | как "побитовое ИЛИ" это было некультурно.
UPD2: Еще одну подсказку могу дать. Для начала реши задачу с условием A[0] <= A[1] <= A[2] ...
тебе не кажется, что эта задача сложнее, чем поставленная?
Как нехорошо.
А я не говорил, что я соблюдаю все правила на CodeForces. Более того, я много их не соблюдал.
Просто д'Артаньян - поборник правил - сам их нарушал.
Здесь: видя | я читаю нотацию Бекуса-Наура, а не битовую операцию.
Кстати, автору: не операнд, а оператор. Операнд - аргумент операции.
Эта задача, только с бОльшими ограничениями недавно была на топкодере. Здесь описано ее решение за O(2N· log(R)· N2).
Сначала решим без учета этого момента. Динамика будет по сл. параметрам [ маска битов суммы чисел][сколько чисел использовали]. Для каждого нулевого бита есть 2 перехода - сделать его единичным для текущего числа, или же начать "собирать" новое число.
Однако, с таким подходом мы можем собрать число большее чем R. Поэтому введем в динамику 2 новых параметра - последний единичный бит, который мы взяли, и идем ли мы по границе самого большого числа. Это накладывает еще одно ограничение, собирать число нужно строго со старших битов к младшим.
Сложность получается (2^18 * 18^2 * 2). Что в принципе должно проходить.
Для каждого нулевого бита есть 2 перехода - сделать его единичным для текущего числа, или же начать "собирать" новое число.
а какие переходы для 1го бита?
Забавный момент. Я прочитал задачу и около получаса думал над нею, (правда дело с просони было, умывался, говолу мыл...) потом собираясь на работу уже не выдержал и посмотрел спойлеры в обусждении, перешёл на 508-ой срм и опппа, у меня 500-ка -то сдана за ~350 баллов. Читал своё решение, и долго не мог понять что-же я там мутил :) потом наконец понял, и успокоился, а мог ведь на час раньше на работу попасть :)