2014
02-12

# Renovation Problem

The New Year’s Day is comming ! Every family want to make theiir house looks more beautiful , so does Teddy’s . To make his own house looks different from other’s , he went to the shop to buy four kinds of tiles . each kind of tiles has different size : 1*1 , 2*2 , 3*3 and 4 * 4, respectively .

The problem is , how many ways there are to tile his floor which has a area of 4*N using these four kinds of tiles ? You can assume that the number of each kind of tiles is enough.

The first line contain a T. followed by T lines ,each line contain a integer N.(1<=N <=100).

The first line contain a T. followed by T lines ,each line contain a integer N.(1<=N <=100).

2
1
2

1
5

/*

简单递推。
注意对于2*n(n>=3)，是可以由2*2的格子交错组合

n=3：
..#
..#
#..
#..
n=4:
….
….
#..#
#..#

2013-01-23
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
int ans[111];
void init()
{
int i,l;
ans[0]=1;
ans[1]=1;
ans[2]=ans[1]+4*ans[0];
ans[3]=ans[2]+4*ans[1]+2*ans[0]+2*ans[0];
for(i=4;i<=100;i++)
{
ans[i]=(ans[i-1]+4*ans[i-2]+2*ans[i-3]+ans[i-4])%19890907;
for(l=3;l<=i;l++)	ans[i]=(ans[i]+2*ans[i-l])%19890907;
}
return ;
}
int main()
{
init();
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%d\n",ans[n]);
}
return 0;
}