It is a very simple problem, just count how many distinct chars in the input and write the correct answer.
First of all we make a table of size a*b*c to store every number's d value. then just brute force though every tripe to calculate answer.
It's a simple problem, but many competitors use some wrong guess and fail.
First of all we should check if n<=3 and then we should output 1,2,6. and if n is odd, the answer is obviously n(n-1)(n-2).
if n is even, of course we can use (n-1)(n-2)(n-3), so these three number wouldn't be very small compared to n. so just iterate every 3 number triple in [n-50,n] and update the answer.
Let us take a deep look in how this score is calculated. for a n long 'O' block, they contribute n 2 to answer.
Let us reformat this problem a bit and consider the following problem.
For each two 'O' pair which is no 'X' between them, they add 2 to score.
For each 'O',it add 1 to score.
We can see that these two problem are exact the same.
for a n long 'O' block,there is C n 2 pair of 'O' in it and n 'O' in it.
2C n 2 + n = n 2.
So for each event(i,j) (which means s[i] and s[j] are 'O', and there's no 'X' between them).
If event(i,j) happen, it add 2 to the score.
So we only sum up the probability of all events and multiply them by 2.
Then our task become how to calculate the sum of all event(i,j).
We can see event(i,j) is simpliy .
Then we denote dp(j) as sum of all event(i,j) and i<j.
so dp(0)=0 and dp(j)=(dp(j-1)+ p j - 1)* p j
This problem can be solved by many suffix structures.
I think suffix automaton is the best way to solve it because it is simple and clear.
So let us build a suffix automaton of the input string S.
And consider the query string x.
let us build a string t to be x concatenate x and drop the last char.
so every consecutive sub-string of t with length |x| is a rotation of x.
let us read string t with suffix automaton we've 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 sus-btring 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 this if you are not familiar with suffix automaton :e-maxx's blog
First of all, let us consider the tree-case.
Let us consider the event like that: "when we select A as deleting point, B is connect to A" to be Event(A,B).
So any happened Event(A,B) would add totolCost by 1.
So we can just simply calculate the probability for every Event, and add them up.
let us consider how to calculate Event(A,B)'s probability.
Assume there's n vertices in path between A and B, 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 happen only if we select vertex A, so the probability is 1 / n.
Otherwise,assume it has x vertices there is two case: 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 orginial case,there's at most 2 paths between A and B.
If there's only one path, then everything is the same with 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 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, they two path from A to B, each path contains a path in cycle, let us call them Y and Z.
So there's two possibility: 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 2 x, 2 y, 2 z , then their upper limit become a / 2 x, b / 2 y, c / 2 z, 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 / p x, b / p y, c / p z, q)·(x + y + z + 1)
Check my code here: 2404223
If you have any problems, you can ask here :)