## 10870 - Recurrences

Moderator: Board moderators

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

### 10870 - Recurrences

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?

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
We can easily speed up the multiplication process... ie, d^3 can be reduced... think about it.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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 ).

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Maybe exists a O(1) algorithm? (small simple formulae )

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### need to learn...

Can someone explain how matrix multiplication is implemented in order to solve this problem?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### thanks..

Thanks to Misof and KP.
..got AC.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

### TLE with Pascal

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:

Code: Select all

ACed

I tried to avoid "Mod m" then I got WA, if you have some large test case please tell me
Last edited by FAQ on Sun Dec 18, 2005 5:09 pm, edited 1 time in total.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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;


FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
Great, I got AC now, thank you a lot, kp

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10870 - Recurrences

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:

Code: Select all

195
206146
1958147
24190


Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10870 - Recurrences

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,

matrix2220
New poster
Posts: 9
Joined: Mon Jul 07, 2014 3:37 pm
Contact:

### Re: 10870 - Recurrences

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


Abdelrahman Ali (MaTrix)