# UVa 10918

From Algorithmist

## 10918 - Tri Tiling

## Summary

Determine in how many ways can a 3xN rectangle be completely tiled with 2x1 dominoes.

## Explanation

It's a typical problem on dynamic programming. One possible solution is described below.

Let be the number of tilings of a 3xN rectangle (which is what we're looking for) and let denote the number of tilings of a 3xN rectangle with one of its corner squares removed.

These functions satisfy the recurrent relations: The formulas can be illustrated as follows:

******** AA******* AA****** A******* ******** = BB******* + B******* + A******* ******** CC******* B******* BB****** f(n) = f(n-2) + g(n-1) + g(n-1) ******** A******** AA******* ******** = A******** + BB******* ******* ******** CC****** g(n) = f(n-1) + g(n-2)

The boundary values for the relations are:

For any odd value of N, the number of tilings of a 3xN rectangle is 0.

## Input

0 1 2 8 12 30 -1

## Output

1 0 3 153 2131 299303201