I can't understand how can it take 1 sec to solve for N = 1000
My biggest ideas is something like a system of equations by modulo 2, but ...
Some hints please...

Please one small pour hint

Please. I still have any ideas. May be finding of circles?

linear module equations will work.
try to rewrite it into a simpler form and you will achieve it!

I found a lot of material about modular arithmetic itself, but nothing about systems of equations modulo 2. There is a problem 1042 that I solved using an intuitive algo. But I don't have any materials about those kind of problems... Any links in Internet are available.

I haven't AC but sure that 1458 is a problem with
great mathematical background.
In matrix language Sulman command is equal to
transformation of tipe A[j]*B*A[k]
where A[j]=diag[1,1,1,...,-1,1,1,1,1..]
So, read about minimal step of transformations to standard form. Also, sequence of such transformation is code
for arbitrary 0-1 matrix. Sure that authors create the problem during reading about 0-1 matrix, transformations and coding.

You're A LOOSER.I've done this program to 1 minute!!!

Each has It's own way and all of us are training to contests.
But even after you words the problem does't seem to me
as simple. Often such quick solutions depend on temporary
weakeness of tests.

Well, then, where is your AC for this problem? You have no AC's at all...

Just find a way to flip some cell without affecting others. It's easy for even N.

Edited by author 03.08.2008 11:31

Ac after some period!
I did'n beleve that O-1 equation method can help.
We have 10^6 unknowns and O(10^18) Gauss.
But I had expierence for large systems with itteration
method(as for  Puasson eqution) and this method works here.

But after I understood that the matrix of the system is
nilpotent because nature of smoothing operator
and itteration method  has right foundation.


Edited by author 10.02.2009 09:24

Thanks!