# PROBLEM LINK

# DIFFICULTY

EASY

# PREREQUISITES

Matrix Exponentiation

# PROBLEM

In how many ways can a fill a matrix of size **a** by **b**, such that, there are no rectanlges of height and width more than 1, that contain only 0s or only 1s.

# QUICK EXPLANATION

Since **a** can only be at most 6, you can consider filling the matrix one column at a time.

A column can be filled in at most **2 ^{a}** ways. You can build an matrix that represents whether a column of type

**A**can be followed by a column of type

**B**. This matrix must be exponentiated

**n**times to get the final answer.

# EXPLANATION

Let us call a rectagle that violates the constraint - that is, it is made up entirely of 0s (or entirely of 1s) and has a width and height, both more than 1 - an invalid rectangle.

It is easy to see that if an invalid rectangle must exist, then there also exists an invalid rectangle of dimensions **2x2**.

Corollarly: if we ensure while filling a column that we are not building an invalid rectangle of dimension **2x2**, then there can never exist an invalid rectangle in the finished matrix.

We are going to fill the matrix column by column.

Consider the following situation.

....................(x0)(y0) ....................(x1)(y1) ....................(x2)(y2) ....................(x3)(y3) ....................(x4)(y4) ....................(x5)(y5)

Let us assume that the matrix has been filled up to column **X** such that it contains no invalid rectangles. We add another column, call it column **Y.** We know that the matrix contains no invalid rectangles of size **2x2** until column **X.** We must ensure that addition of column **Y** does not add an invalid rectangle of dimension **2x2.**

But since any **2x2** rectangles that addition of column **Y** can introduce can only at most overlap column **X,** we can ignore the state of the rest of the matrix!

Now, let **Bx = (x5, x4, x3, x2, x1, x0)** be the bitset that represents the values in column X. Similarly, let **By = (y5, y4, y3 y2, y1, y0)** represents the values that we intend to fill in column Y.

**Y can follow X if and only if (Bx bitwise-and By) does not contain any consecutive 1s AND (Bx bitwise-or By) does not contain any consecutive 0s**.

We can no build a matrix **canFollow** of dimension **2 ^{a}** by

**2**which represents whether some configuration of a column can be followed by another configuration in the next column.

^{a}Exponentiation of **canFollow** leads us to enumerating the number of ways of filling the columns such that the matrix does not contain any invalid rectangles. As an example, the **4x4** matrix for a = 2 is

00 01 10 11 00 | 0 1 1 1 | 01 | 1 1 1 1 | 10 | 1 1 1 1 | 11 | 1 1 1 0 |

Adding all the values in the above matrix gives us the answer for **a = 2, b = 2**.

To get the answer for **a = 2, b = 3** - we multiply it with itself once.

| 3 3 3 2 | | 3 4 4 3 | | 3 4 4 3 | | 2 3 3 3 |

The answer would thus be 50.

The answer for and **a** and **n** can similarly be found by raising the matrix of dimension **2 ^{a}** by

**2**to the power

^{a}**(n-1).**

# SETTERS SOLUTION

Can be found here.

# TESTERS SOLUTION

Can be found here.