Contest has ended, and I'd like to share my approach to last problem — White Falcon and XOR. It took me almost two days to invent, and it differs from the one in editorial.

Suppose we already know about dynamic programming that runs in 64 * N * (N - 1) / 2 — for every possible value of xor-sum (which can be 0..63) keep number of ways to produce it. When we want to extend current segment to the right, update DP in the following manner:

for val in range(64):
  next[val ^ a[position]] += dp[val]
  next[val ^ b[position]] += dp[val]
for val in range(64):
  dp[val] = next[val]
  next[val] = 0

(position is the endpoint of current segment).

Now we want to speed this up. We can notice that:
1. When we xor numbers 0..63 with a number X, we get numbers 0..63 in shuffled order (the only exception is X = 0, which does not permute anything).
2. Since we have exactly 64 states in our DP, we can denote it as a single unsigned long long value. Actually, we will keep track of what states are "reachable", i.e. dp[v] = 1 if we can achieve a xor-sum equal to v, else dp[v] = 0.
3. Let's look at DP updates separately for array a and array b. Good news are, "reachable" DP states are either "reachable" in one case, or in both. In other words, we can't possibly have dp[i] updated by, for example, a[position], but not updated by b[position].
4. Xor operation with a fixed value V can be viewed as shuffling some blocks of lengths 2ⁱ, where i-th bit is set in V. For example (with integers up to 7):
x: 0 1 2 3 4 5 6 7
x^6: 6 7 4 5 2 3 0 1
We can do this in two steps (subject to 6 = 110₂):
- Permute two blocks of length 2² = 4: 4 5 6 7 0 1 2 3
- Now switch places of every pair of blocks of length 2¹ = 2: 6 7 4 5 2 3 0 1
Therefore, we can use some bit operations with unsigned long long's to compute out modified DP and get all "reachable" states. The pseudocode is like:

get_next_state(state, V):
  for i in 5..0:
    if i-th bit is set in V:
      low_half = state & 11..100..011..100..0 // here each block of same bits has length 2 ** i
      high_half = state & 00..011..100..011..1
      state = (low_half shl 2 ** i) OR (high_half shr 2 ** i)
  return state

Taking point 4 into account, we now can see for each segment L..R whether 0 can be reached. It takes 6 * N * (N - 1) / 2 operations to do that.
Now remember point 3. It implies that every original DP state have value of the form 2^k, and it can only be increased. Let's keep track of current k. When L = R set k = 0. Then, if the modified state for a[position] is equal to modified state of b[position], increase k by one. Otherwise, it stays the same.

My code for reference: link. It runs in 1.73 seconds almost on all testcases.

I have not author's solution for last problem too.

At first, let's say that we have another two sequences: a and c, where c_i = a_i ^ b_i. Then element of sequence w_i will be either a_i or a_i ^ c_i ( = b_i).

So the answer for segment [L, R] (number of sequences w₁, w₂, ..., w_{R - L + 1} such that w₁ ^ w₂ ^ ... ^ w_{R - L + 1} = 0) will be number of subsequences of c such that c_i1 ^ c_i2 ^ ... ^ c_ik = a_L ^ a_L + 1 ^ ... ^ a_R, L ≤ i₁ < i₂ < ... < i_k ≤ R. Why so? Suppose we have elements from b in w with indices i₁, i₂, ..., i_k and w₁ ^ w₂ ^ ... ^ w_{R - L + 1} = 0. We can replace every b_j with a_j ^ c_j and get a_L ^ a_L + 1 ^ ... ^ a_R ^ c_i1 ^ c_i2 ^ ... ^ c_ik, that is equivalent to c_i1 ^ c_i2 ^ ... ^ c_ik = a_L ^ a_L + 1 ^ ... ^ a_R.

Let's fix left end of segment on i-th position and move right one from i to n. We can notice that now problem is similar to knapsack problem, which could be solved in O(N·MAX), where MAX is the maximum value of a_i (64). But it's not enough, O(N²·MAX) is too much.

Suppose L is left end of our segment, i is current right end.

We can denote such interesting fact: if we had c_i before in our segment (among c_L, c_L + 1, ..., c_i - 1), then it's easy to calculate new values of dynamic: every value will be increased twice.

Why is it so? Suppose we have k values of c_i before. How many are there subsequences with even number of occurences of c_i? X·(C_k⁰ + C_k² + C_k⁴ + ...) = X·2^k - 1, because we should choose even number of places, where we take c_i in our subsequence.

And after i-th index we have k + 1 values of c_i. Similarly, number of subsequences with even number of occurences of c_i will be X·(C⁰_k + 1 + C²_k + 1 + C⁴_k + 1 + ...) = X·2^k = 2(X·2^k - 1). Similarly with odd number of occurences.

It's obvious that we are interested only if number of occurences is odd or even, not exactly in number.

Finally, solution is so: we fix left end of segment and move right end. If we meet new value, we calculate dynamic in O(MAX), otherwise we increase counter twice. Events of first type could happen at most MAX times, so we have O(N·(N + MAX²)) solution.

For more details see code