SPOJ Problem Set (classical)
2159. Delicious Cake
Problem code: CAKE3
Lenka likes to bake cakes since her childhood, when she has learned to bake from
her mom. She soon became a cake expert able to bake chocolate cakes, apple
pies, muffins, cookies, cheese cakes, tortes and many other cakes.
Recently, she has started her studies of math at Comenius University in
Bratislava. In the first year she is taking combinatorics class. Today she is
studying for the final exam. Since the brain needs a lot of sugar to study math,
she has baked, just for herself, her favorite, very delicious, strawberry cake.
The cake, still hot, is lying on an N◊M inch sheet pan.
Hungrily waiting for the cake to cool off Lenka came up with an interesting combinatorial question:
How many different possibilities to cut the cake are there so that every
connected piece consists of some number of 1◊1 inch unit squares?
The cake can be viewed as a grid consisting of N◊M unit squares.
We are allowed to cut the cake along the grid lines. As a result the cake splits into
several connected pieces. (Two unit squares remain connected
if they share a side which was not cut.) How many different ways are there to cut the cake?
We consider two cuttings of the cake to be the same if the resulting connected pieces
of both cuttings have the same shape and are at the same positions within the cake.
In other words, we are only counting those cuttings where no cut leads between two
unit squares that are in the same connected piece.
The following picture ilustrates all the 12 different possible ways how to cut a 2◊2 inch cake:
Note that cutting, for example, as on following picture
is the same as not cutting at all.
The first line of the input file contains an integer T
specifying the number of test cases.
Each test case is preceded by a blank line.
Each test case consists of a single line with two positive integers N and M – dimensions of the cake.
For each test case output a line with a single positive integer – the number of
different possibilities how to cut the cake.
For all the test cases, min(N,M)<=5, max(N,M)<=130.
Blue Mary's Note: The data has been enhanced on Feb.28, 2008 to avoid precalculated tables. Sorry to some users.