Help, here is my code, and I don't know why WA#4((
[deleted]

Edited by author 01.02.2007 03:06

Pls...

When I made a quick look at your solution I've seen such mistakes:
1. Part of your code in function pow_matrix

for(int i = 0;i < p/2; i++)
sqr_matrix(a,b,n);

As I can guess this function has to put matrix A to the power of p. But the thing you do is - write the square of A into B many times. Your result is always square of A (not the power p)!!!
It seems, that you wanted to sleep when wrote this solution :-)

2. If you do all calculation like you do now you will get Type Overflow. That is because the numbers in A^50 can be as large as 10^100 - that does not fit in integer type (no even in Int64 ;-) ).

Correct 1. And think about 2. And you will get AC!
...if not TL :-)

Try to use bool matrix.
You would get certanly overflow, so some unneeded 0 may occur duting addition.
Also you will certnaly get TLE. If you use bool matrix, then after some of multiplication, it won't chage more, so in most cases it is not even nessery to multiply till the end and add.
During the context we solved this problem without any pow, just with :
for(int i = 1; i < n*(n-1); ++i)
mult_matrix();
for(int i = n*(n-1); i < n*(n+1); ++i){
mult_matrix();
add_matrix();}
keeping in ming the chaging state of matrix. However, later some thicky test were added, so now it's ge TLE, so some more improvements are needed, but it can be passed also.

Edited by author 01.02.2007 02:40

Thank's to all.  I'll try it)

To Ostap: I had done some changes, but now WA5 :-(

[deleted]

Edited by author 05.02.2007 14:58

Are you sure 10^100 fits __int64 ? I think not. Read the previous post by Lomir - he explains everything pretty clearly.

Second. For example if p == 6 then you calculate ((A^2)^2)^2 == A^8 != A^6
Think about it.

Edited by author 02.02.2007 02:29

The same problem, I'm getting WA4. Please give some tests. I'm using boolean matrix, all seems to be pretty clear

Got AC. Problem was in matrix multiplication, very stupid one! So when you're getting WA4, it's probably just multiplication problem

Thank's to all. I had done it and got AC now:).

My WA4 was about wrong identity matrix initialization (filled in 2x2 of ones instead of NxN :P)