For all who are asking why O(N^4 * 10) is been accepted! So answer is that there is a chance of weak test cases in 1< = T <= 10. May be all test cases would not able to cover N=70. otherwise in execution speed it impossible to get AC in (10^8 * 2) instruction according to the question!
http://www.codechef.com/viewsolution/7297553
My solution was something like finding maximum sum submatrix in which instead of Kadane i use Trie based solution to find maximum xor subarray.
According to me complexity of this solution certainly looks better than O(n^4) to be exact O((n^3)*32).But still I got TLE for 2nd subtask.And was one major reason i didn’t use O(N^4) solution.
Can someone help me where am i going wrong??
@franky Notice that method which I described in the editorial takes about O(N^4 / 4) with a very small constant
@yashv For O(N^3) you can first compute table row[N][N]] where, row[i][j] = a[i][0] ^ a[i][1] ^ … ^ a[i][j] and col[j][i] = a[0][j] ^ a[1][j] ^ … ^ a[i][j]. These tables can be computed in O(N^2). In the C table we have O(N^2) entries and you can compute C[i][j] in constant time xoring C[i - 1][j] with row[i][j]
2 Likes
How can we neglect 10 test cases! O(N^4) is required for precomputaion for every test case. So, how does that solution passed in 1 second and trie tree implementation got tle(I accept that constant is small for that O(N^4) solution. Plz explain! 
Thanks. That helped.
Please refer to tester’s solution for N^2 preprocessing