uva 10918-Tri Tiling(法則)

タイトルリンク:uva 10918-Tri Tiling
nを与えて、1*2のタイルでどれだけの方法で3*nの地方を敷き詰めるかを計算します.
解題の構想:uva 10359-Tilingと少し似ているが、難易度は比較的に大きく、公式c[i]=4*c[i-2]-c[i-4].
導出過程:c[0]=1,c[2]=3,c[4]=c[2]*3+c[1]*2,c[6]=c[4]*3+(c[0]+c[2])*2.....
すなわち、c[i]=c[i−2]*3+2*Σ(0≦j≦−4)c[j]であり、前述の式に持ち込んで簡略化することができる.

#include <stdio.h>
#include <string.h>
#define ll long long

ll n, c[35];

void init() {
	memset(c, 0, sizeof(c));
	c[0] = 1;
	c[2] = 3;
	for (int i = 4; i <= 30; i++)
		c[i] = 4 * c[i - 2] - c[i - 4];
}

int main() {
	init();
	while (scanf("%lld", &n), n!= -1) {
		printf("%lld
", c[n]);
	}
	return 0;
}