Nhân ma trận với bài LATGACH4(spoj)

Nhân ma trận với bài LATGACH4(spoj)

Ta định nghĩa đơn giản phép nhân ma trận như sau:

Phép nhân mảng A[M,N| và B[N,P] được mảng C[M,P] và mỗi phần tử C[i,j] được tính theo công thức:

            C[i,j]:=  Σ A[i,k]*B[k,j];

Sau đây là các bài toán áp dụng nhân ma trận và tính chất của nó.

 Link bài : LATGACH4(spoj)

Cho một hình chữ nhật kích thước 2xN (1<=N<10 1x2="" 2x1="" a="" c="" ch="" cho="" di="" g="" h="" i="" k="" kh="" l="" m="" n="" ng="" ngo="" nh="" o:p="" o="" ph="" ra="" s="" sao="" style="box-sizing: border-box;" t.="" t="" th="" tr="" v="" vi="" y="">

Input

Gồm nhiều test, dòng đầu ghi số lượng test T ( T<=100 ). T dòng sau mỗi dòng ghi một số N.

Output

Ghi ra T dòng là số cách lát tương ứng lấy phần dư cho 111539786.

Example

Input:

3

1

2

3

Output:

1

2

3

Hướng dẫn:

Trước hết ta có thuật toán O(n) như bài LATGACH

< http://vn.spoj.com/problems/LATGACH/ >

               F[1]:=1;

               F[2]:=2;

               F[i]:=F[i-1]+F[i-2]; if i>2

Nhưng ta nhận thấy với n<=10^9 thì thuật toán O(n) là không khả thi. Vì vậy ta có thể dựa vào công thức để dùng phép nhân ma trận giải quyết bài toán trong O(logn). Ta có mảng A với A[1,1]=F[i-1]; A[1,2]=F[i] và ta phải thực hiện nhân mảng A với mảng B để được mảng C có C[1,1]=F[i] và C[1,2]=F[i+1]. Từ đó ta suy luận được mảng B sẽ là :
                                             

0	1
1	1

function        nhanmatran(A,B:mang):mang;

var     i,j,k:byte;

        D:mang;

begin

        fillchar(D,sizeof(D),0);

        for i:=1 to 2 do

                for j:=1 to 2 do

                        for k:=1 to 2 do

                                D[i,j]:=(D[i,j]+(A[i,k]*B[k,j]) mod base) mod base;

        exit(C);

end;

Sau khi tìm được mảng B, ta phải thực hiện nhân n-2 lần để tìm ra F[n] -> thuật toán vẫn là O(n). Nhưng ta lại có thể lợi dụng tính chất giao hoán của phép nhân để giảm độ phức tạp:
               ((((A*B)*B)*B)….)*B = A* B^n;

Ta sẽ thực hiện phép lũy thừa B^n trong logn rồi mới nhân mảng A với mảng B^n:

Function               lt(n:longint):mang;

Var         D:mang;

Begin

               If n=1 then exit(B);

               D:=lt(n div 2);

               D:=nhanmatran(D,D);

               If n mod 2=1 then exit(nhanmatran(D,B)) else exit(D);

End;

->           C:= nhanmatran(A,lt(n-2));

Kết quả :         F[1]=1;

F[2]=2;

F[n]=C[1,2] if n>2;

 Như vậy thuật toán sẽ là O(số test*2^3*logn) đủ để pass.