Блог пользователя Light_Yagami

Автор Light_Yagami, 13 лет назад, По-русски
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

  • Проголосовать: нравится
  • -33
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -24 Проголосовать: не нравится
    Что за глупость! Мне нужны идеи и алгоритмы. Если не знаете решения, зачем показывать себя умным!?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -12 Проголосовать: не нравится
      Ладно, конкретизирую. Если ограничение на каждое число у тебя до 150000, то какое у тебя ограничение на ответ? Правильно, до 150000*10.
»
13 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится
Я даже незнаю какой алгоритм использовать! )
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Если расписать числа в двоичном виде, можно заметить, чтобы сумма чисел была равна xorу этих же чисел, то для каждой позиций всех чисел количество 1 должно быть не больше одного.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится
      Это-то понятно! ) Но дальше?
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Так как R небольшое можно перебрать все числа от 0 до R, и для каждого этого числа прибавить к ответу N^количество единичных бит в числе, как то так.

        UPD неверный алгоритм

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

          Во-первых, не перебрать, если вы говорите о 15000010 - это явный ТЛ.

          Вот придумать на основании того что уже сказано выше какой-нибудь алгоритм, работающий за UPD: видимо log(R)*R*N.
          А дальше не палить контору. Он сам сумеет разобраться дальше, разжевыванием только помешаем.

          UPD2: Еще одну подсказку могу дать. Для начала реши задачу с условием A[0] <= A[1] <= A[2] ...
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Ой, | как "побитовое ИЛИ" это было некультурно.

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            UPD2: Еще одну подсказку могу дать. Для начала реши задачу с условием A[0] <= A[1] <= A[2] ...

            тебе не кажется, что эта задача сложнее, чем поставленная?

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

            А я не говорил, что я соблюдаю все правила на CodeForces. Более того, я много их не соблюдал.
            Просто д'Артаньян - поборник правил - сам их нарушал.

            Здесь: видя | я читаю нотацию Бекуса-Наура, а не битовую операцию.

            Кстати, автору: не операнд, а оператор. Операнд - аргумент операции.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      вроде там не xor, а or
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Эта задача, только с бОльшими ограничениями недавно была на топкодере. Здесь описано ее решение за O(2N· log(RN2).

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно решить динамикой. Заметим, что максимальное число содержит 18 бит (15000010 = 1001001001111100002). Однако, мешает один момент. В сумме, мы можем получить число большее чем максимально разрешенное (R).
Сначала решим без учета этого момента. Динамика будет по сл. параметрам [ маска битов суммы чисел][сколько чисел использовали]. Для каждого нулевого бита есть 2 перехода - сделать его единичным для текущего числа, или же начать "собирать" новое число.
Однако, с таким подходом мы можем собрать число большее чем R.  Поэтому введем в динамику  2 новых параметра - последний единичный бит, который мы взяли, и идем ли мы по границе самого большого числа. Это накладывает еще одно ограничение, собирать число нужно строго со старших битов к младшим.

Сложность получается (2^18 * 18^2 * 2). Что в принципе должно проходить.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

     Для каждого нулевого бита есть 2 перехода - сделать его единичным для текущего числа, или же начать "собирать" новое число.

    а какие переходы для 1го бита?

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Забавный момент. Я прочитал задачу и около получаса думал над нею, (правда дело с просони было, умывался, говолу мыл...) потом собираясь на работу уже не выдержал и посмотрел спойлеры в обусждении, перешёл на 508-ой срм и опппа, у меня 500-ка -то сдана за ~350  баллов. Читал своё решение, и долго не мог понять что-же я там мутил :) потом наконец понял, и успокоился, а мог ведь на час раньше на работу попасть :)