这次我们用2 * 1的地板砖来铺地，地是一块3 * n的矩形，你能告诉我有多少种铺地的方案么？

 

Input

本题有多组测试数据，每组测试数据包含一个正整数n（0 <= n <= 40)。

Output

对于每组测试数据输出铺地的种类数。

Sample Input

4

5

6

Sample Output

11

0

41

题意：略，正常人能看懂。

题解：看到例子5输出0，仔细思考，只要是奇数都是0，偶数自己画出2的来，然后结合例子，推出公式，公式是什么呢，看代码，就能懂，上代码：

#include <iostream>
using namespace std;
typedef long long ll;
ll a[50];
void init(){
	a[0]=1;//这个需要初始化为1，很容易想到
	a[1]=0;
	a[2]=3;
	for (int i = 3; i <= 40;i++){
		if(i&1) a[i]=0;
		else a[i]=a[i-2]*4-a[i-4];//递推式
	}
}
int main(){
	init();
	int n;
	while(cin >> n){
		cout << a[n] << endl;
	}
	return 0;
}