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

How to solve this combinatorics problem ?
Автор sandeep007, история, 5 лет назад, По-английски

Given the frequency of each lowercase character f(a), f(b)... f(z) and k. Compute the number of unique strings of length k having sorted characters.

k <= 10^5

Sum(f(i)) <= 10^5

Please provide Hints/Approach to solve this problem.

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

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

Is that a stars and bars problem!

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

Let's make a dp state that is (current char, string index) that stores the count. When we move to the next char, we need the sum of the last f(char) items for our new value at a given index. We can calculate these in O(1) by doing a prefix sum on the last row of our dp.

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

    This is $$$O(k)$$$?
    What if there are $$$Q \le 10^5$$$ queries of this type with different frequencies and $$$k$$$?

    → Ответить