It is a very simple problem, just count how many distinct chars in the input and output the correct answer.
First of all, we can make a table of size a*b*c to store every number's d value. Then we can just brute force through every tripe to calculate the answer.
It is a simple problem, but many competitors used some wrong guesses and failed. First of all, we should check if n is at most 3 and then we can simply output 1,2,6.
Now there are two cases: When n is odd, the answer is obviously n(n-1)(n-2). When n is even, we can still get at least (n-1)(n-2)(n-3), so these three numbers in the optimal answer would not be very small compared to n. So we can just iterate every 3 number triple in [n-50,n] and update the answer.
Let us take a deep look at how this score is calculated. For an n long 'O' block, it contributes n2 to the answer.
Let us reformat this problem a bit and consider the following alternative definition of the score: (1) For each two 'O' pair which there is no 'X' between them, they add 2 to the score. (2) For each 'O', it adds 1 to the score.
We claim that this new definition of the score is equivalent to the definition in the problem statement.
Proof of the claim: For an n long 'O' block, there are Cn2 pairs of 'O' in it and n 'O' in it. Note that 2Cn2 + n = n2.
So now we work with the new definition of the score. For each event(i,j) (which means s[i] and s[j] are 'O', and there is no 'X' between them). If event(i,j) happens, it adds 2 to the score.
So we only need to sum up the probabilities of all events and multiply them by 2, and our task becomes how to calculate the sum of probabilities of all the event(i,j). Let P(i,j) be the probability of event(i,j).
We can see that P(i,j) can be computed by . Then we denote P(j) as the sum of all event(i,j) for i<j. We have dp(0)=0 and dp(j)=(dp(j-1)+pj - 1)*pj
This problem can be solved by many suffix structures. Probably using suffix automaton is the best way to solve it since suffix automaton is simple and clear.
Let us build a suffix automaton of the input string S, and consider the query string x.
Let us also build a string t as x concatenated with x dropping the last char. One can see that every consecutive sub-string of t with length |x| is a rotation of x.
Let us read the string t with suffix automaton we have build, and every time take the first char out and add a new char, add the answer by the number of string equal to this current sub-string of t (which is a rotation of x).
And one more thing, we should consider the repetend of x as well, check my solution here:2403375.
Check here if you are not familiar with suffix automaton :e-maxx's blog
First of all, let us consider the simpler case of trees.
Let us use Event(A,B) to denote the following event "when we select A as the deleting point, B is connected to A".
Clearly, if Event(A,B) happens, it would add 1 to totolCost.
So we can just simply calculate the probability of every Event(A,B), and add them up.
Let us consider how to calculate the probability of Event(A,B).
Assume there are n vertices in the path between A and B, we claim that the probability is simply 1 / n.
Let us try to prove it using induction.
First let us assume there's a connected sub-graph of the tree containing both A and B, if the sub-graph only has n vertices, then the event happens only if we select vertex A, so the probability is 1 / n.
Otherwise, assume it has x vertices there is two cases: whether the selected vertex is on the path between A and B or not.
In the first case, the probability of Event(A,B) happen is 1 / x because if we don't select A, Event(A,B) will never happen.
In the second case, the sub-graph containing A,B has become smaller, so the probability is (x - n) / xn.
So add them up we can prove this statement.
Then we can solve the tree case by simply add up the inverse of every path's length in the tree.
And for the original case, there's at most 2 paths between A and B.
If there's only one path, then everything is the same with the tree case.
Otherwise, the path between A and B should pass the cycle in the graph.
Let us examine this case, you can see that there 2 types of vertex:
Vertex on the path of A to cycle or B to cycle, they should not be selected before A because once they're selected, A and B lost connectivity, let us call them X.
Vertex on the cycle, the two paths from A to B, each path contains a path in the cycle, let us call them Y and Z.
So there are two possibilities: X and Y are free when A is selected, X and Z are free when A is selected.
And we should subtract the case that X and Y, Z are all free when A is selected because it double-counts before.
So the probability is 1 / (X + Y + 1) + 1 / (X + Z + 1) - 1 / (X + Y + Z + 1).
And my C++ implementation: 2403938
Let us consider each prime in one step, the upper limit for a, b, c is recorded.
So if we fixed the power of 2 in each i, j, k like 2x, 2y, 2z, then their upper limit becomes a / 2x, b / 2y, c / 2z, and the power of 2 in their multiplication is just x+y+z.
Let us denote dp(a, b, c, p) for the answer to the original problem that i, j, k 's upper limit is a, b, c. And their can only use the prime factors which are not less than p.
Let the next prime to be q, so we can try to fix the power of p in i, j, k and get the new upper limit.
So we can do transform like this: dp(a, b, c, p) = sum of dp(a / px, b / py, c / pz, q)·(x + y + z + 1)
Check my code here: 2404223
If you have any problems, you can ask here :)