This was my logic during the contest. Consider each of the cells as a point and we connect cell A and B with an edge if

1. they're adjacent, and
2. they have the same color.

Note that no edges can share their endpoints ( otherwise, a cell should share its color with two or more neighboring cells ).

Also note that if a cell at coordinate (x, y) is connected with (x, y + 1), then (x + N, y) and (x + N, y + 1) are also connected for all valid integer N ( This can easily be seen by assuming each of their color ). The same holds for the case where (x, y) is connected with (x + 1, y).

Now we see that there are no cases where there are both horizontal and vertical edges. So our answer is (The number of shapes where there are no horizontal edges) + (The number of shapes where there are no vertical edges) — (The number of shapes where there are no edges).

Now the number of shapes where there are no horizontal edges are completely determined by the state of the first column by our previous observation. And this number is eactly the N-th fibonacci number times two (The number of the positionings of the edges are F_n, and you can alternate color for each cases).

The second term is M-th fibonacci number times two similarly.

The last term is obviously 2.

Therefore, the answer is (F_n + F_m — 1) * 2

Some observations:

• if you repeat some color horizontally, you cannot repeat any color vertically, and vice versat
• if you repeat some color horizontally, the colors of all cells in the whole 4-columns slice is defined uniquely

Let's count the number of "horizontal colorings".

Define $$$d_{k}$$$ the number of horizontal colorings of the first $$$k$$$ rows (no matter how many columns there is).

There are two options to fill $$$k$$$-th row:

1. Fill each cell with the opposite color of the upper cell: $$$a_{ij} = \bar{a}_{i-1 j}$$$
2. Fill each cell with the same color of the upper cell: $$$a_{ij} = a_{i-1 j}$$$

In addition, you cannot apply the $$$2^{nd}$$$ option more then twice in a row. It's easy to see that other "mixed" variants break the rules.

Let's assume that the first row is filled in some correct way. Therefore, the number of horizontal colorings $$$d_{k} = d_{k-1} + d_{k-2} = f_{k}$$$ The same formulae stands for vertical colorings.

The only coloring that presents in both of vertical and horizontal colorings is pure chess coloring.

And you need to multiply the result by 2 because you defined the first row in some fixed way and colors can be the opposite.

Here's a late reply but maybe people who will see this editorial in the future will find it helpful.

Consider that you have a valid coloring for the first row, you will notice that the coloring of this row enforces the coloring of the entire grid. Similarly for the first column. We have (-1) since the case where white and black alternates in each row and in each column is counted twice (with F(n) and with F(m)). **** Answer = T(n,m) = 2 * (F(n) + F(m) — 1)

Where F(x) is the number of ways we can fill a (1 by x) grid using blocks of size 1x1 and blocks of size 1x2. If x >= 2, we can choose to put a 1x1 block at the beginning (we're left with F(n-1) choices) or put a 1x2 block at the beginning (we're left with F(n-2) choices) -> F(n) = F(n-1) + F(n-2) -> Fibonacci!!

(Note: Equivalent to the problem where you're asked to the find the number of ways to climb n stairs if you can at each step go to the next level or to the one next to the next level).

We multiply the factor (F(n) + F(m) — 1) by 2 since flipping black and white will keep the grid coloring valid.

Great explanation.

Can you please elucidate a bit?

Why do we need to pick SCCs?

your recursive tree goes exponentially, and that probably causes memory overflow

Time complexity of recursive Fibonacci is exponential.

I demand you to stop RIGHT THERE NO STOP You're calculating nth fibonacci number explicitly NO STOP

MOD IT EVERY TIME YOU CALCULATE PLEASE

Also you did not use memoization try this

M = 10 ** 9 + 7 # MODULO
array = [0] * 100010 # Extra because im bad
array[0] = 1
array[1] = 1
# array[2] = 2
def f(n):
    if array[n] == 0:
        array[n] = (f(n — 1) + f(n — 2)) % M
    return array[n]

# To initialize, don't use sys.setrecursionlimit(99999). It's bad.
for i in range(1, 100010):
    f(i) # Calculates the value but doesn't do anything with it
# Now you can do
# a, b = tuple(map(int, input().split()))
a, b = map(int, input().split()) # No need tuple, python is smart :)
print (( (f(a)+f(b)-1)*2 ) % M)

We reduce $$$cnt$$$ if we see "(" and increase $$$cnt$$$ if we see ")".

Let's calculate it on example: "))()(())(("

Cnt: [-1, -2, -1, -2, -1, 0, -1, -2, -1, 0]

The minimum of all $$$cnt$$$ (-2 here) is when we close all levels of brackets. Then we increase it again (opening new levels) and closing them, checking if we again closed all levels (when $$$cnt$$$ = minimum).

Also we should check if last $$$cnt = 0$$$ (it means that we find opposite brackets for starting).

Hope you understand it better)

It is written on higher level than most of div2 participiants could understand.

C editorial should be extended as for me.

Awesome! Didn't know about the problem you refer to, It turns that giving problems for contests is very useful sometimes.

Let's fill the first row in some correct way. Then, the way you fill all the other rows is forced (this is the key observation for the problem). So, to get the answer to the problem you actually just need to find the number of ways to fill the first row (the first "strip").

There are some technicalities. Let's assume that the top left cell is always white. We will need to multiply the eventual answer by 2 to account for symmetry (when the top left cell is black).

Let $$$f(k)$$$ be the number of ways to fill a "strip" of length $$$k$$$.

1) We fill the first row. The number of ways for this is $$$f(n)$$$. All other rows depend on the first row.

2) We fill the first column. The number of ways for this is $$$f(m)$$$. All other columns depend on the first column.

3) Notice that both in 1) and 2) we count the "chess board" case, where the color of every cell is different to all its neighbors'. This is why we subtract 1, because we want to count each board state exactly once.

We now have a total of $$$f(n) + f(m) - 1$$$ ways. We multiply by 2 to account for the case where the top left cell is black (and thus flip the colors of all cells). So the answer is $$$2*(f(n) + f(m) - 1)$$$.

The only thing left to do is to find out how to calculate $$$f(i)$$$ for some $$$i$$$. I think this is literally one of the simplest ways to use dynamic programming.

$$$f(0) = 1$$$

$$$f(1) = 1$$$

$$$f(i) = f(i-2) + f(i-1)$$$ for $$$i \geq 2$$$

You should split 2n-2 items. Two smallest will be start and finish.

It's overkill because you can just sort the elements in $$$O(n log n)$$$. But since $$$a_i \leq 10000$$$ you can use counting sort and solve it in $$$O(n + maxa)$$$.

my comment

I realized bfs can solve my problem

My solution O(n^3)

As you can see it passed with 732 ms. I dont see much (or any) difference in our solution. So i guess, please submit the solution again with

#pragma GCC optimize("Ofast")

at first just as i used and also change endl to \n (it also saves time)

if u still get tle, try chaning cin and cout to scanf and printf respectevly. (Although i dont think TLE will come)

no...i think its beacuse chessboard case is included in both (no two same colored adjacent cells)