Hello and welcome to codeForces.

Today’s choice is the last and most difficult question in Div3 competition. The main reason for choosing this question is to help build everyone’s confidence, because some friends told me that the previous topic was a little difficult and they thought they might not be able to deal with codeForces. So today I specially chose the hardest problem in the Div3 competition to give you a little confidence.

Div3 competition is the least difficult competition, for the algorithm of beginners, very suitable for everyone as a beginner practice. Since it was the last question, the number of people who passed this question was not very many, about 530. But this question is not very difficult, I feel it is about the same as our QUESTION C in Div2.

Link: https://codeforces.com/contest/1426/problem/F


Without further ado, let’s cut to the chase.

The question

Given a single ABC and? Of the string, where? Can be arbitrarily substituted for a, B, or C. Let’s say, right? There are k of them, so we can get a total of different strings.

The number of SUBsequences of ABC in all of these strings, which are subsets of the original string that can be obtained by deleting elements without changing the relative order of the elements. For example, baacbc has two subsequences of ABC, subscript combinations (2,5,6) and (3,5,6).

Since the final quantity may be large, this result is required to be modulo.

The sample

There are two lines of input. The first line is given an integer n(), which represents the length of the string. The second line is a string of length N that returns the number of ABC subsequences.


An explanation of the first example:


Answer key

This one looks complicated, and it’s not easy to come up with a solution to attack it head on. So let’s put a couple of things aside and start with the simplest idea.

The simplest case

First of all, we need to solve a problem, which is when there is no? How do we find the number of subsequences of ABC? For example, acABAC, how do we figure out the number of subsequences of ABC? The answer is 2. Where does this 2 come from?

Since b comes after A and C comes after B, we could of course just use a triple loop to enumerate all combinations, but that’s not the best way to do it. If we think about it, this is a limited combinational problem, and it’s easy to see that every letter B can form a pair of ab with all the a before it, and every letter C can form a subsequence of ABC with every sequence ab before it.

So we can use the idea of dynamic programming to solve, we use three variables D [0], D [1], D [2], respectively maintain the number of a, AB and ABC strings. When we meet a, d[0] plus 1, what about when we meet B? D [1] plus 1? Obviously not, since b can form ab with every previous A, d[1] should add d[0] instead of 1. Similarly, when c is encountered, d[2] should be added to d[1].

So we can figure out if there are any? Is the number of subsequences that satisfy the condition.

d = [0.0.0]



for i in range(n):

    if s[i] == 'a':

        d[0] + =1

    elif s[1] = ='b':

        d[1] += d[0]

    else:

        d[2] += d[1]

Copy the code

Use the advanced

Have we worked it out now? What happens when it happens, plus? What should I do?

Let’s take it a step further. For each of these? There are really three options for it. Such as a? C, you have aAC, ABC, and ACC. So can we meet again? Take all three into account?

When we meet? “, let’s copy the d array into three copies and store them separately. Okay? =a, ? = b and? Is equal to c. Let’s first copy array D into d1, d2, and d3. We’re going to use these three arrays, right? You take three different values, and then you merge them together to make a new array, d_new.

Because d1, D2, and D3 are just D, so when we put them together we can still write them as D.


There’s no problem here, right? There’s a trick here. This trick is very subtle and hard to spot. Is it us? In the case of =a, d1[0] += 1 is actually not the right thing to do, we’re not adding 1. Let’s take an example, for example, a? C.

We have two in this string, right? For the first one? In terms of, it’s a when d[0] += 1 and that’s fine. But when it comes to the second? The problem is, for the case where the first question mark is equal to a, since the second question mark has three values, the number of a brought in should actually be 3, not 1. We just added 1 and it was an error. We can also go the other way. For the first question mark, we integrate three possibilities. When we set the second question mark to a, there are actually three possibilities behind the first question mark, so instead of adding a 1, we add a 3. What if we have three question marks? The third question mark is obviously 9. In other words, for the KTH question mark,

Trick noticed that AC was a natural thing.

n = int(input())

s = input()



ret = 0

Mod = int(1e9+7)



dp = [0.0.0]

cnt = 1



for i in range(n):

    if s[i] == 'a':

        dp[0] += cnt

    elif s[i] == 'b':

        dp[1] += dp[0]

    elif s[i] == 'c':

        dp[2] += dp[1]

    else:

        dp[2] = (3 * dp[2] + dp[1]) % Mod

        dp[1] = (3 * dp[1] + dp[0]) % Mod

        dp[0] = (3 * dp[0] + cnt) % Mod

        cnt = (cnt * 3) % Mod





print(dp[2] % Mod)

Copy the code

Today’s choice is the one with the least number of people passing div3 competition, which is the most difficult one. But when we do it, we find that we actually use the most basic idea of dynamic programming, and it’s not easy to figure out the solution, but it’s actually quite easy.

So if you want to improve your algorithmic skills, but are worried that the problems are too difficult for you, consider doing some competitions in DIV3. Trust me it won’t be too hard.

That’s all for today’s article. I sincerely wish you all a fruitful day. If you still like today’s content, please join us in a three-way support.

Original link, ask a concern