Page 1 of 1
10870 - Recurrences
Posted: Tue Jun 28, 2005 2:24 am
by kp
I solved this problem using matrix multiplication.
The complexity of my algorithm is about
d^3*log(n/d) = O(logN). d <= 15 by the statement.
My program runs in 0:00.326 s.
Are there any other (faster) algorithms?
Maybe some tricks?
Posted: Tue Jun 28, 2005 9:29 am
by Dreamer#1
We can easily speed up the multiplication process... ie, d^3 can be reduced... think about it.
Posted: Tue Jun 28, 2005 12:02 pm
by kp
Yes, I thought about that, but I think that using FFT to find
matrix product of matrices not bigger than 15x15 is like
"shouting birds from the cannon" (I don't know the english
equivalent of this russian proverb, sorry
).
Posted: Tue Jun 28, 2005 12:32 pm
by kp
Maybe exists a O(1) algorithm? (small simple formulae
)
Posted: Tue Jun 28, 2005 12:42 pm
by misof
Well, most probably there's nothing much better than the solution with matrices. The general form of the solution is something along the lines:
Code: Select all
n-th term = \sum_{i=1}^d y_i (x_i ^n)
where x_i are the roots of the characteristic polynomial of the recurrence and y_i are coefficients depending on the initial values.
need to learn...
Posted: Wed Jun 29, 2005 11:24 am
by sohel
Can someone explain how matrix multiplication is implemented in order to solve this problem?
Posted: Wed Jun 29, 2005 12:59 pm
by misof
Posted: Wed Jun 29, 2005 1:06 pm
by kp
Let
1. F(n) = A(1)*F(n-1)+...+A(d)*F(n-d).
2. F[k*d] = column (F(d*(k-1)+1), F(d*(k-1)+2), ..., F(k*d)), k=1..infinity
It's not difficult to find quadric matrix A of size d, that
F[2*d] = A*F[d]
The main property of the matrix A is that for every k>0 we have
F[(k+1)*d] = A*F[k*d] , so
F[k*d] = A*F[(k-1)*d] = A*A*F[(k-2)*d] = ... = A^(k-1)*F[d] , k>0
So to find F(n) you should calculate M-th power of A, where M
is ((n-1) div d), after that you multiply row ((n-1) mod d)+1 of this matrix
to the column Start (initial values) and get the answer.
P.S.:
Of cource, we can get the N-th power of quadric matrix of size d
for the d^3*log(N).
[EDIT]: misof is faster
thanks..
Posted: Sat Jul 02, 2005 3:44 pm
by sohel
Thanks to Misof and KP.
..got AC.
TLE with Pascal
Posted: Sun Dec 18, 2005 6:44 am
by FAQ
Someone who have got AC with Pascal please help me
I used algorithm with O(d^3logN) but I still got TLE, I think MOD operation in Pascal is too slow.
Can we multiply 2 matrixes faster than this one:
I tried to avoid "Mod m" then I got WA, if you have some large test case please tell me
Posted: Sun Dec 18, 2005 4:43 pm
by kp
I used this routines:
Code: Select all
type
TMatrix = array [1..15, 1..15] of integer;
..............
function MatrixMul(const A, B: TMatrix): TMatrix;
var
i, j, k: integer;
begin
for i:=1 to d do
for j:=1 to d do begin
result[i,j]:= 0;
for k:=1 to d do begin
inc(result[i,j],(A[i,k]*B[k,j]) mod m);
result[i,j]:= result[i,j] mod m;
end;
end;
end;
function MatrixPow(const A: TMatrix; pow: integer): TMatrix;
var
i: integer;
begin
fillchar(result,sizeof(result),0);
if pow=0 then begin
for i:=1 to d do result[i,i]:=1;
end else if pow=1 then result:= A
else begin
B:= MatrixPow(A,pow div 2);
B:= MatrixMul(B,B);
if odd(pow) then
result:= MatrixMul(A,B)
else result:= B;
end;
end;
Posted: Sun Dec 18, 2005 5:08 pm
by FAQ
Great, I got AC now, thank you a lot, kp
Re: 10870 - Recurrences
Posted: Sat May 21, 2011 10:23 pm
by Shafaet_du
Nice problem to learn matrix exponentiation(You should try 10229 first though).
Try this:
Code: Select all
6 345345 443
999999 12443434 3214234 34535 456456 21424
7676 435 34 78 34 23
10 4468895 231123
9999 122344 321743 3412 12156 223424 23345555 76 222 12213
7676 435 34 78 34 23 456 8979 2323 2345
18 412455 2334523
9999 999999 12443434 3214234 34535 456456 21424 122344 321743 3412 12156 223424 23345555 76 222 12213 234 666
7676 435 34 78 34 23 7676 435 34 78 34 23 456 8979 2323 2345 23445 6666
1 3455 100007
17
23
0 0 0
out:
Re: 10870 - Recurrences
Posted: Sat May 21, 2011 10:26 pm
by Shafaet_du
Slight mistake in above input. D should be less than 15 but i gave 18. but ac codes should be able to pass it i think,
Re: 10870 - Recurrences
Posted: Tue Sep 09, 2014 5:25 pm
by matrix2220
Hint:
Code: Select all
| f(n+1) | | a1 a2 ...... ad | | f(n) |
| f(n) | | 1 0 0 .... 0 | | f(n-1) |
| . | = | 0 1 0 .... 0 | * | . |
| . | | .............. | | . |
| f(n-d+1) | | ...........1 0 | | f(n-d) |
Generalization:
| f(n+k) | | a1 a2 ...... ad |^k | f(n) |
| f(n+k-1) | | 1 0 0 .... 0 | | f(n-1) |
| . | = | 0 1 0 .... 0 | * | . |
| . | | .............. | | . |
|f(n+k-d+1)| | ...........1 0 | | f(n-d) |
Answer is f(n+k) , k = n-d