Here is the link to the problem : https://www.quora.com/Can-you-share-some-trickest-coding-questions-that-you-have-faced-in-any-coding-contest/answer/Rishabh-Jain-2492

There is N x M matrix filled with 0 and 1 only, lets say a matrix is special if every 2 x 2 sub matrix in it has two 0’s and two 1’s . Find the total number of special matrices you can have for N x M.

On the hunt of an efficient solution.

The answer is$$$2^n+2^m-2.$$$

Why?You can notice that all special matrices have very similar form:

СпойлерOr the same thing but rotated by 90 degrees. For example:

So each row/column is either 101010... or 010101...

However matrices like

1010

0101

and

0101

1010

(alternating rows / columns)

can be represented both ways so we subtract two.

Unfortunately, I'm not able to come up with proof for this.

But you can verify it using bruteforce.

P.S. This problem is similar to 1099E - Хорошая таблица

Hint for a proofkostia244's "form" that all special matrices fit is equivalent to saying "there are either adjacent equal pairs in the X-direction or the Y-direction, but not both". Assume there's an adjacent horizontal pair of the same color somewhere, and an adjacent vertical pair of the same color somewhere, and try to reach a contradiction.

Further hints/the restIf you have a horizontal pair of cells of the same color, then the cells directly above them have to be the other color, and so on, so that entire pair of columns has to be alternating, like this:

If you also have a vertical pair of the same color, then an entire pair of adjacent rows has to be alternating. Where this vertical double-column and horizontal double-row overlap, you have a contradiction.

Thanks! Your hint really helped me and I was able to prove it.

By the way, if you are interested in a slightly similar problem, check out 1178C - Плитки.