Link:http://codeforces.net/gym/100020 F This is an interesting problem,and main idea seems simple but hard to find it out. First we can find for each cell when we perform an rotate operation there are four cells related to it: (i,j),(i,n-1-j) (n-1-i,j),(n-1-i,n-1-j)

so we can use only (n-1)/2*(n-1)/2 matrix to record the state of each cells. There are 6 states of each cell:

00 11 11 00 10 01

00 11 00 11 10 01

and further more, when we perform each rotate operation, the result is swap two of these six states. so for each cell,the result of any times of operation is the permution of the six states,for brute force idea we just need to record per[6] for every cells,of course,brute force will timeout,and obviously we need a data structure such as two dimension segment tree with lazy labels for each big matrix(we need to use the permuation of these 6 states as lazy labels). and for every time we visit the big father matrix,we need to pass the lazy labels to the son matrix.we need to convert son.per[6],and fa.per[6] as son.per[i]=fa.per[son.per[i]].

This idea we two dimension segment tree worst complexity is m*n*log(n),this is not the problem,but the problem is memory is too much,so we need to compress the 4000*4000 matrix into 500*500==250000 (8*8) bigger matices and for when we visit matrix which is smaller or equals to 8*8 just run a brute force(use a char mat[4001][4001] to record which constant factor is much smaller than segment tree).

This idea makes me 5300+ms AC, but I don't know if there are any more sufficient data structure to implement this idea