PROBLEM LINK:
Author: Roman Furko
Testers: Pushkar Mishra and Sergey Kulik
Editorialist: Pawel Kacprzak
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng
DIFFICULTY:
Easy
PREREQUISITES:
bits, implementation
PROBLEM:
You are given a square matrix A of size N. For a submatrix B of A, we define its value as the bitwise XOR of all elements of B. Your task is to find the maximum value among all submatrices of A.
QUICK EXPLANATION:
Since N \leq 70, if we are able to compute a value for a given submatrix in constant time, we can iterate over all submatrices and return the maximum value. In order to compute the value for a given submatrix fast, we first compute values of all submatrices which have the upperleft corner at (1, 1). Then we can use these values to compute every other value using properties of XOR operation.
EXPLANATION:
Let C[i][j] be the value of the submatrix which has its upper left corner at (1, 1) and its bottom right corner in (i, j). We can compute the C table in O(N^4) or O(N^3), or even O(N^2), but since N is quite small, it does not matter which method you choose.
After that, we notice the major property of XOR, i.e. x \oplus x = 0. Using this property and precomputed table C, we can easily compute the value for any submatrix R in constant time. Let’s consider the below illustration and define 5 submatrices:

R, the Red submatrix, we are
interested in computing its value 
B, the Blue submatrix, we have its
value computed and stored in C
table 
G, the Green submatrix, we have
its value computed and stored in C
table 
Y, the Yellow submatrix, we have
its value computed and stored in C
table 
P, the Purple submatrix, we have
its value computed and stored in C
table
Let’s define, for the above matrices, C_X to be the value from C table for a submatrix X, for example C_R is the value of the matrix R. Then C_R = C_B \oplus C_G \oplus C_Y \oplus C_P
This is duo to the major property of XOR and the fact that both C_G and C_Y contain C_P as a submatrix.
Time complexity
For a single test case it is O(N^4) because we can compute the C table in O(N^4); and we compute the value for every submatrix in a constant time, and there are O(N^4) different submatrices.