Lightoj 1244 - Tiles

Problem Link:
Explanation:

As we can see here the tiles can not be rotated, so it actually made the problem much simpler.Here goes a little analysis of the problem. We will define 3 functions as follows.

we assume that f(n) is the answer, so

 f(n) = f(n-1) + f(n-2) + g(n-2)+h(n-2),  here f(n-1) because of the vertical tile

f(n-2) because of the horizontal shaped tile and we must use 2 of them reducing to n-2

we assume g(n-2) is similar to f(n-2) accept there is a square in the top corner and this pattern is found when we use type 3 tiles and the symmetric case h(n-2) is same as g(n-2) except this time  that square is in the bottom and this patter is found when we use type 4 tile. So we found the basic function but what is g(n) and h(n) in our known terms?? 

g(n) = f(n-1) + h(n-1); as we can use tile 4 and find structure f(n-1) or we use a horizontal type 2
tile in the bottom and find structure like h(n-1)

h(n)  = f(n-1) + g(n-1) similar case.

 for better visualization go here

so the basic matrix goes like  

[ 1 1 1 1 ]      [  f(n-1) ]     [   f(n)    ]

[ 1 0 0 0 ]  *  [  f(n-2) ] =  [  f(n-1)  ]

[ 0 1 0 1 ]      [ g(n-2) ]     [  g(n-1) ]

[ 0 1 1 0 ]      [ h(n-2) ]     [  h(n-1) ]

Here goes the code: 

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define llu long long unsigned
4. #define MOD 10007
5. llu cm[4][4];
6. void mul(llu a[4][4],llu b[4][4]){
7.     memset(cm, 0, sizeof(cm));
8.     for(int i = 0; i <4; i++){
9.         for(int j = 0; j <4; j++){
10.             for(int k = 0; k <4; k++){
11.                 cm[i][j]+= ((a[i][k]%MOD)*(b[k][j]%MOD))%MOD;
12.                 cm[j][j]%=MOD;
13.             }
14.         }
15.     }
16.     for(int i = 0; i <4; i++){
17.         for(int j = 0; j <4; j++){
18.             a[i][j] = cm[i][j]%MOD;
19.         }
20.     }
21. }
22. void ans(llu p[4][4], llu n){
23.     llu m[4][4] = {{1,1,1,1},{1,0,0,0},{0,1,0,1}, {0,1,1,0}};
24.     if(n == 1) return;
25.     ans(p, n/2);
26.     mul(p, p);
27.     if(n%2) mul(p, m);
28. }
29. int main(){
30.     int ts;
31.     scanf("%d", &ts);
32.     for(int p = 1; p <= ts; p++){
33.     llu n;
34.     scanf("%llu", &n);
35.     //printf("Case %d:\n", p);
36.     llu f[4][4] = {{1,1,1,1},{1,0,0,0},{0,1,0,1}, {0,1,1,0}};
37.     llu answer1;
38.     if(n == 1) answer1 = 1;
39.     else if(n == 2) answer1 = 2;
40.     else ans(f, n-2),answer1 = (f[0][0]*2)%MOD+f[0][1]%MOD+f[0][2]%MOD+f[0][3]%MOD;
41.     printf("Case %d: %llu\n",p, answer1%MOD);
42.     }
43.     return 0;
44. }