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

Комбинаторика
Автор ironsoul, история, 7 лет назад, По-русски

Есть n объектов. Для каждого объекта известно его количество a[i], которое у нас есть. Сколько различных последовательностей длины len можно составить из имеющихся объектов.

Это обычная комбинаторика? Есть ли какая-то формула? Спасибо.

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

»
7 лет назад, # |
← Rev. 6   Проголосовать: нравится -7 Проголосовать: не нравится

Похоже на размещение с повторениями (если важен порядок элементов в последовательности), или сочетание с повторениями (если не важен порядок).

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

А какие ограничения на n и len? Может там зайдёт динамика вида dp[i][x] =  число различных последовательностей длины x составленных из объектов, номера которых не больше i.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    n <= 16, len <= 8, a[i] <= 10

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      При таких ограничениях можно просто перебор написать. Перебираешь сколько возьмешь i-го типа, и к ответу прибавляешь .

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Откуда все берет такие фотографий, типа len!/(cnt1!*..*cntn!) или O(NlogN).

        → Ответить