Though I have realized there might be some math-method to solve the problem, I couldn't find them out. So, I just solve the problem "the way it tells me to do".

To prevent high-precision (Chinese name of long-arithmetic), I use this method: I choose many factors and calculate the power of the matrix with the module of the factors. So, if one cell is 0 under all the factors, we can ALMOST assert that the cell is indeed 0.

To prevent TLE, the factors could not be so many: I choose 10 factors first, that is 16384 (2^15), 19683 (3^9), 15625 (5^6), ... until 24389 (29^3). My program runs well but get TLE @ test 17.

So, I decrease the factors to only TWO: 16384 and 19683. This time my program get WA @ 9! I think I really appreciate the author for so good test-data.

After that I increase my factors to 4, adding 15625 and 16807. This time I got AC in 0.64s.

Funny problem, thx to the author.
Have fun and good luck.

Hehe, you're CRAZY man...
I just used boolean matrix.

Edited by author 03.10.2010 02:10

Well, before I decided to use this CRAZY method, I have read all the topics on board, but I still can't understand the meaning of BOOLEAN MATRIX.

Could you or anyone explain it to me?

Input: a[i][j] = readInt() > 0;

Then use && instead of * and || instead of +.

If result contains at least one false value, write "No".

P.S. I don't believe my eyes! You have 400+ problems solved and couldn't guess this simple approach!

Edited by author 06.10.2010 22:22

Well, just after reading your post, I read the problem statement again.
I found that I had ignored the fact that all the number is non-negative. (So stupid mistake)

Thank you.