Contest Duration: - (local time) (100 minutes) Back to Home
Official

## F - XOR on Grid Path Editorial by en_translator

Let us call the exclusive logical sum XOR and denote the XOR of non-negative integers $$x$$ and $$y$$ by $$x \oplus y$$.

There are $$\binom{2N - 2}{N - 1}$$ ways to travel from square $$(1, 1)$$ to $$(N, N)$$; in this problem, there are at most about $$3.5 × 10^{10}$$ ways. Thus, trying all of them does not finish in the time limit.
Instead, we use the trick called meet-in-the-middle. Roughly, we try to optimize the program by corresponding $$S$$ objects into the direct product set of two sets of sizes about $$\sqrt{S}$$ and process them.

When traveling from square $$(1, 1)$$ to $$(N, N)$$, you pass through a unique square on the squares on the anti-diagonal line, that is, a square $$(x, y)$$ such that $$x + y = N + 1$$. For one path, let $$p$$ be the XOR on the squares in the path from square $$(1, 1)$$ to $$(x, y)$$, and $$q$$ be that from square $$(x, y)$$ to $$(N, N)$$; then the path satisfies the condition in the problem statement if and only if $$p \oplus a_{x, y} \oplus q = 0$$.

Therefore, let $$P$$ be the multiset of the XORs of the integers written on each path from square $$(1, 1)$$ to $$(x, y)$$, and $$Q$$ be the counterpart from $$(x, y)$$ to $$(N, N)$$, then the number of paths satisfying the conditions in the problem statement passing through square $$(x, y)$$ equals the number of pairs $$(p, q)$$ such that $$p \in P, q \in Q$$, and $$p \oplus a_{x, y} \oplus q = 0$$. This can be found by sorting or binary search in a total of $$O((|P| + |Q|) \log (|P| + |Q|))$$ time.

Since $$|P| = |Q|$$, and the sum of $$|P|$$ over all squares $$(x, y)$$ on the anti-diagonal line is $$2^{N - 1}$$, the problem has been solved in a total of $$O(N2^{N})$$.

posted:
last update: