Understanding At Coder Problems (Colorful Subsequence)

Asked 4 months ago, Updated 4 months ago, 10 views

I don't understand the problem with the atcoder below.
https://atcoder.jp/contests/agc031/tasks/agc031_a

I looked at the explanation and the AC code, and found that c[each character - 'a']++ in the size 26 int array
However, I didn't understand if repeating A.Answer*=c[i] would produce the desired output.
I would appreciate it if you could explain it in detail.

-
Problem statement
A string S of length N is given.
Please answer the remainder of the column S divided by 10^9+7 by the number of characters that are different characters.Even if they are identical as strings, you should count them separately from each other.

However, a string substring is a string that takes a few positive characters out of the string and connects the original string without changing the order.

Restrictions
1 NN 100100000
S is lowercase letters

Enter
Inputs are given from standard input in the following format:

N

S

Output

Number of substrings of different characters 10
9
+
7
Print the remainder divided by .

Input Example 1
4
abcd
Sample Output 1

--
▼Explanation

Even if it is the same string, all sub-columns of 2N-1 will be distinguished because they are differentiated from each other.
Since the same characters must not be used twice, the way to keep the colorful conditions for a character c is (number of times c appears +1) (the case where one of them is taken and the case where no character c is taken)
Find the product of this method for all characters c and subtract one-third of the empty string for the answer.

See AtCoder Grand Contest 031

java algorithm

2022-09-30 14:15

1 Answers

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.


2022-09-30 14:15

If you have any answers or tips


© 2023 OneMinuteCode. All rights reserved.