There is.

The equal subsequence can't contain numbers from [p1 + 1, p2 — 1] so you should choose len — 1 numbers from the remaining ones. Btw, there's editorial here(scroll down to english version).

It seems that I just solved it (5 minutes after the contest because of some stupid bug). I have no idea why it works though...The main observation is that if you had an even string of length 2S with P equal to the maximum length of a prefix strictly smaller than S that is also a suffix, than you go from (S, P) to (2S — P, S — P). This happens by actually getting the half of the given array as Q, and than consequently doing the operation Q += the first S — P elements of Q (here |Q| = S always)And somehow, these numbers seem to be increasing exponentially. To actually get the answer, I did a recursive function that transforms an interval of level L in at most 2 smaller of level L — 1, where level 0 is the given string. However, it failed even on the samples. In order to make it pass, it was enough to keep continuous segments with the same coefficient. You could check my source for better understanding (it has the old, too slow, recursive function too).

Notice that for any number a[i], the sequence of positions (position after every operation) is given by the recurrence:

T(n) = T(n-1)+ i*(n%2==0)-(i-1)*(n%2==1)

So, for number a[i], find x = T(n-i+1) and set b[x] = a[i].

Let's think about the small case.

n = 1: a[1]
n = 2: a[2] a[1]
n = 3: a[3] a[1] a[2]
n = 4: a[4] a[2] a[1] a[3]
n = 5: a[5] a[3] a[1] a[2] a[4]
n = 6: a[6] a[4] a[2] a[1] a[3] a[5]
n = 7: a[7] a[5] a[3] a[1] a[2] a[4] a[6]
n = 8: a[8] a[6] a[4] a[2] a[1] a[3] a[5] a[7]

Do you realize it?

• If n is odd, the first half part is all odd number, and decreasing sequence. And the latter part is all even number, and increasing sequence.
• If n is even, the first half part is all even number, and decreasing sequence. And the latter part is all odd number, and increasing sequence.

It is after the Japanese editorial in pdf.

The sequence length is n + 1, and each of the integers 1,…,n appears in the sequence. So there is exactly one pair that the number is the same.

First, let's consider about the entire patterns.
The number of patterns that if the contents of two subsequences are the same, they are separately counted, is C(n+1, k).

Second, let's consider about the number of subsequence which is the same.
Consider the pattern of {1, 2a, 3, 4, 2b, 5}. (2a, 2b is both 2.)

• {2a} and {2b} is the same.
• {1, 2a} and {1, 2b} is the same.
• {2a, 5} and {2b, 5} is the same.
• {1, 2a, 5} and {1, 2b, 5} is the same.

http://e-maxx-eng.appspot.com/combinatorics/binomial-coefficients.html
you can use some formulas
for problem D,
http://e-maxx-eng.appspot.com/algebra/module-inverse.html
or precalculate all k!(mod M) and k!^- 1(mod M) for k ≤ N in O(N)

You C++ code, you can check this and this.

For Python code, you can check this