T1.6 Những con ong

Những con ong

Tổ ong gồm là những hình lục giác đều được xếp khít nhau. Mỗi hình lục giác đều kề cạnh với 6 hình lục giác đều khác. Con ong chúa được ở trong trung tâm của tổ. Nó muốn đi dạo quanh khu vực tổ ong để thăm các con ong khác. Nó sẽ đi đúng N bước, bắt đầu từ tổ của nó và cũng kết thúc tại tổ của nó. Bạn hãy đếm xem nó có bao nhiêu cách đi như vậy. Biết rằng nếu đi từ tổ của nó, sau N bước không bao giờ đi ra ngoài tổ ong.


Dữ liệu vào ONG.INP gồm duy nhất một số N.
Kết quả in ra file ONG.OUT mỗi dòng ghi một số là số cách đi của con ong chúa sau khi mod 1 tỷ.
Ví dụ
ONG.INP
2
ONG.OUT
6
ONG.INP
3
ONG.OUT
12
Giới hạn: N ≤ 50

Code:

#include<bits/stdc++.h>
#define ll long long
#define N 101
using namespace std;
const ll h=1e9;
ll dx[6]={0,1,1,0,-1,-1};
ll dy[6]={1,0,-1,-1,0,1};
ll d[N][N][N]; int n,u0,v0; ll tmp;
void solve(){
   u0=v0=n/2+1;
   d[0][u0][v0]=1;
   for(int i=1; i<=n; i++)
      for(int u=1; u<=n+1; u++)
         for(int v=1; v<=n+1; v++){
            tmp=0;
            for(int j=0; j<=5; j++)
               tmp=(tmp+d[i-1][u+dx[j]][v+dy[j]]%h)%h;
            d[i][u][v]=tmp;
         }
   cout<<d[n][u0][v0];
}
int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   cin>>n;
   solve();
   return 0;
}