# UVa 10918

From Algorithmist

## Contents |

## [edit] 10918 - Tri Tiling

## [edit] Summary

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

## [edit] Explanation

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

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

These functions satisfy the recurrent relations:
*f*(*n*) = *f*(*n* - 2) + 2*g*(*n* - 1),*g*(*n*) = *f*(*n* - 1) + *g*(*n* - 2).
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:
*f*(0) = 1,*f*(1) = 0,*g*(0) = 0,*g*(1) = 1.

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

## [edit] Input

0 1 2 8 12 30 -1

## [edit] Output

1 0 3 153 2131 299303201