Threads: http://vn.spoj.pl/problems/M3TILE/

Count the way paved by 3XN rectangular domino 2×1?

The input contains several testcase ends of -1.
Each testcase is an integer n, 0 ≤ n ≤ 30.
For each test case, in the integer is the answer in a row.
SAMPLE INPUT
2
8
12
-1
SAMPLE OUTPUT
3
153
2131
Time: 1with
Attention: n = 0 is returned results 1.

This article is for odd n, the number of cells 1×1 is odd when you are domio 2 umbrella, their sum is always even, the result is the problem returns 0 there is no way to put the appropriate. Thus we only consider the n even.
First consider the rectangle 3×2, easily noticed 3 placing

At the next rectangle 3×4, 3 x 3 = 9 from + 2 a => 11 from

At the next rectangle 3×6, we have the following cases:

If the call f(to) is a slice of rectangular 3xk, we have:
f(6) = f(2) * f(6-2) + 2*[ f(6-4) + f(6-6) ] = 3*11 + 2*(3+1) = 41 from.
General have:
f(to) = 3*f(k-2) + 2*[ f(k-4) + f(k-6) + .. + f(0) ]
=> f(to) + f(k-4) = 3*f(k-2) + 3*f(k-4) + 2*[ f(k-6) + f(K-8) + .. + f(0) ]
=> f(to) + f(k-4) = 3*f(k-2) + f(k-2) = 4*f(k-2)
=> f(to) = 4*f(k-2) – f(k-4)
So we have found the formula retrieval briefly as follows:
f(to) = 4*f(k-2) – f(k-4) with f(0) = 1, f(2) = 3
f(n) is a solution to the problem. Install the following (time: 0.01s 🙂 )

#include<stdio.h>
int main()
{
    int n,i;
    int f[31]={0};
    f[0]=1;
    f[1]=0;
    f[2]=3;
    f[4]=11;
    for(i=6;i<=30;i+=2)
       f[i]=4*f[i-2] - f[i-4];
    scanf("%d",&n);
    while(n!=-1)
    {
       printf("%dn",f[n]);
       scanf("%d",&n);
    }
    return 0;
}