There is currently no feature that allows you to change your old password to a custom one, sorry.

try to send clarification request

Proof is easy. Let its xor sum be X. Then for each element a in that interval we must have a^(2ⁿ - 1)^X also is in that interval. So we have d pairs (a, a^(2ⁿ - 1)^X). Because its xor sum is X, so X must be 0.

Denote N = 2^M - 1.

You can answer the queries of the type "maximum/minimum index i such that N - perm[i] exists in the target interval" in O(1) with O(NlogN) or even O(N) precomputation with RMQ. Then, if the answer to any of the queries doesn't belong to the target interval, the interval is winnable (as explained in chemthan's post).

Unfortunately, as the task is to count the winnable intervals rather than answer to queries, this method is only O(N²), which is enough only for 50% of the points.

Sure, let's first think about the game in a different light. Suppose that everything on the grid stays still and the main character can in one second move from (r, c) to (r - 1, c - 1), (r - 1, c) or (r - 1, c + 1). It is easy to see those games are equivalent.

Let dp[r][c][o] denote the longest valid expression you can acquire if you are currently on position (r, c) on the screen and the difference between the number of open parentheses and closed parentheses in the expression you have acquired thus far equals o. Computing all dp values takes O(R³) time. This solves the part of the problem that deals with the length of the sequence.

For the reconstruction, we'll keep around a set of dp states that can potentially lead us to the lexicographically smallest solution. At the beginning, that set contains only Mirko's initial position. We will now make transitions from those states (similar to transitions in dp) that lead to longest solutions and traverse only the empty cells of the grid (this is a standard bfs). Once we have exhausted the empty cells, we have obtained the set of cells that contain the next parenthesis in our sequence. At this point we will disregard all cells that have ')' written on them in case there exists a single cell with '(' written on it. Repeating this process yields the lexicographically smallest sequence in O(R²).

Im not sure simple bfs was the optimal way. My code was not that simple

really ,it is a simple bfs.

I don't know, but it reminded me this problem: http://mirror.codeforces.com/contest/877/problem/D