4058:ACM Puzzles

問題文
http://livearchive.onlinejudge.org/external/40/4058.pdf

縦3横nの長方形が、与えられた回転できないブロックで作る方法がいくつあるか求めよ。

f[ n ]:=横nの長方形の場合の数
とする。
g1[n],g2[n],g3[n],g4[n]についてはそれぞれ以下のような図形の場合の数とする。
以下の図は全てn=5の場合である。

g1
.****
.****
*****

g2
.****
*****
.****

g3
.****
*****
*****

g4
*****
.****
*****

のようにすると、下のコードのような式が立つ。
以下の図の左辺の形は、右辺の*の形の部分に
AまたはBの形のブロックを付け加えて作ることができる。

 f[n]  =  f[n-1] + g1[n-1] + g1[n-1] + g2[n-1] + g3[n-1] + g3[n-1] + g4[n-1]
*****     A****     AA***     A****     AA***     AA***     A****     A****
*****  =  A****  +  AA***  +  AA***  +  A****  +  A****  +  A****  +  AA***
*****     A****     A****     AA***     AA***     A****     AA***     A****

 g1[n] =  f[n-2] + g3[n-2]
.****     .A***     .A***
.****  =  .A***  +  .A***
*****     AA***     AAA**

 g2[n] =  f[n-2] + g4[n-2]
.****     .A***     .A***
*****  =  AA***  +  AAA**
.****     .A***     .A***

 g3[n] =  f[n-2] + g1[n-1] + g1[n-3]
.****     .A***     .A***     .AAB*
*****  =  AA***  +  AA***  +  AABB*
*****     AA***     A****     ABB**

 g4[n] =  f[n-2]
*****     AA***
.****  =  .A***
*****     AA***

#include<iostream>
#include<algorithm>
#define MAX 2001
#define MOD 1000000000000LL

using namespace std;

typedef long long ll;

ll f[MAX],g1[MAX],g2[MAX],g3[MAX],g4[MAX];

int main(void){
  
  f[0]=f[1]=1;
  
  for(int i=2;i<MAX;i++){
    g1[i]+=f[i-2]+g3[i-2];
    g2[i]+=f[i-2]+g4[i-2];
    g3[i]=f[i-2]+g1[i-1];
    if(i>2)g3[i]+=g1[i-3];
    g4[i]=f[i-2];
    f[i]+=f[i-1]+g1[i-1]*2+g2[i-1]+g3[i-1]*2+g4[i-1];
    
    f[i]%=MOD,g1[i]%=MOD,g2[i]%=MOD;
    g3[i]%=MOD,g4[i]%=MOD;
  }
  
  int n,tc=0;
  while(cin >> n,n)
    cout << "Case "<< ++tc <<": "<< f[n] << endl;
  
  return 0;
}