Sgu P131铺地板

题目描述:

The banquet hall of Computer Scientists' Palace has a rectangular form of the size M x N. It is necessary to lay hardwood floors in the hall. There are wood pieces of two forms:

1) rectangles (2x1)

2) corners (squares 2x2 without one 1x1 square)

You have to determine X - the number of ways to cover the banquet hall.

Remarks. The number of pieces is large enough. It is not allowed to leave empty places, or to cover any part of a surface twice, or to saw pieces.

题意:一个大小M*N的矩形可由两种地板（2*1,L型）来铺，求有多少种方案数。一定要铺满，地板之间不能有重合，地板也不能分割。

输入格式:

The first line contains natural number M. The second line contains a natural number N.

输入有两行，第一个行一个数M，第二行一个数N。

输出格式:

First line should contain the number X, or 0 if there are no solutions.

输出只有一行，一个数表示方案数。如果不存在，输出0。

样例输入:

2 3

样例输出:

5

提示:

时间限制: 1000ms
空间限制: 256MB

---

来源: sgu