Understanding At Coder Problems (Colorful Subsequence)

To be honest, I don't really understand what "Explanation" means.You should ignore it until you understand the content.

First of all, can you understand that in the output example 1 (if all characters are different), 2^N-1 (^ is the power of power, not XOR)?

For example, N = 4, so 2^4-1 = 15 is the answer.

In this way of thinking,

In this question, the "sub-column" (different from the usual commonly used meaning "sub-column") is

 a, b, ab, c, ac, bc, abc, d, ad, bd, abd, cd, acd, bcd, abcd

There are 15 types of , but even if you don't actually make these 15 types, you can only count them if you know how to think.

a(a)use　　, b Don't use, c don't use, d don't use)
 b(a, b, c, d)
ab(a, b, c, d)
  c(a, b, c, d)
a(a, b, c, d)
 bc(a, b, c, d)
abc(use a, use b, use c, use d)
   d(a not used, b not used, c not used, d not used　　)
ad(a use, b use, c use, d use　　)
 bd(a, b, c, d, d, d, d, d, d, d, d, d.　　)
abd(a use, b use, c use, d use　　)
  cd(a, b, c, d, d, d, d, d, d, d, d, d.　　)
ad(a use, b use, c use, d use)　　)
 bcd(a not used, b used, c used, d used　　)
use abcd(a)　　, use b, use c, use d　　)
-------------------------------------------
     (a not used, b not used, c not used, d not used) Does not apply to the definition of "sub-column" in this question

There are two choices for each character a, b, c, d (use, not use), which is 4 characters, so the total number is 2×2×2×2×2=16. However, since all characters contain "not use", you subtract 1 and get 15 characters.

With this in mind, regardless of which alphabet you use, do you understand that you can calculate the total number of characters if you only know how many types of characters there are?

Let's take a look at sample output 2 during the question.

For the input string baa,

b, a(first a), a(second a), ba(first a), ba(second a)

There are five types of , so you have to answer 5.

If you look at it the same way as above, it looks like this.

b(use b, do not use a)
 a(I don't use b, I use a first one)
  a(I don't use b, a2nd one)
ba(Use b, a 1st)
ba (use b, use a second)
------------------------
    (b not used, a not used) Does not apply to the definition of "sub-column" in this question

You can see thatFor characters b that appear only once, you can subtract 1 from 5 because there are two types of characters b that appear (use, use, use, use, use) and a that appear only once (use, use, use, use) and the total number is 2x3=6.

Considering the output example 3 in the same question, since the string is abcab, 2 a, 2 b, and 1 c, the answer is 17 by subtracting 1 from the total number of 3×3×2=18.

In other words, if you know the number of times a character appears, that (number of times +1) represents the number of times it is related to that character.

For characters that do not appear at all, if you set the value of array c[] to 1, you can multiply all the elements of c[] without dividing them because x1 is the same as doing nothing.

The int array c[] of the code you saw may mean that the initial value of all elements is set to 1, or that all elements are added to 1 after counting.

I hope you understand.If there is something difficult to understand, please let me know exactly which part you don't understand, and I might be able to write more details.