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

Автор _Untrackable_, история, 15 месяцев назад, По-английски

Is there any way to tell the no of subsequences of a given string with all unique elements.. I had used recursion but gets TLE. anyone have any optimal answer?

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

use pnc

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i am unable to reply back on codeforces currently

it says-"daily quota of 3 recepeints exceeded"

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Count the number of appearances of each character, let's store them in an array $$$c$$$, such that $$$c_1$$$ is the number of a's, $$$c_2$$$ is the number of b's, and so on. Now, for each character, we can either choose one of its appearances and add it into a subsequence, or not add the character at all. So we have $$$c_i+1$$$ possibilities for character $$$i$$$. Now we just multiply the number of possibilities for each character and we get the result.