10870 - Recurrences

[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?

[Dreamer#1]

We can easily speed up the multiplication process... ie, d^3 can be reduced... think about it.

[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 ).

[kp]

Maybe exists a O(1) algorithm? (small simple formulae )

[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.

[sohel]

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

[misof]

Read my last post in this thread: http://online-judge.uva.es/board/viewtopic.php?t=6757

[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

[sohel]

Thanks to Misof and KP.
..got AC.

[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:

Code: Select all

ACed

I tried to avoid "Mod m" then I got WA, if you have some large test case please tell me

[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;

[FAQ]

Great, I got AC now, thank you a lot, kp

[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:

Code: Select all

195
206146
1958147
24190

[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,

[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