Just Bumping it . In case someone wanna help .

Think about the last row of the tower. You can either have both cells as a part of the same block, or both cells as parts of different blocks. Let's call towers of the first kind type-1 towers, and the towers of the second kind type-2 towers.

Let's call $$$a_n$$$ be the number of type-1 towers and $$$b_n$$$ be the number of type-2 towers.

For computing $$$a_n$$$, look at what remains when you remove the last row from the tower. Corresponding to a type-1 tower of height $$$n - 1$$$, there will be two such towers, and corresponding to a type-2 tower of height $$$n - 1$$$, there will be one such tower, so $$$a_n = 2a_{n - 1} + b_{n - 1}$$$. In a similar manner you have $$$b_n = 4b_{n - 1} + a_{n - 1}$$$.

Then you can either precompute the answers to all possible queries, or use matrix exponentiation to solve the recurrence. The answer is $$$a_n + b_n$$$.

can someone tell me the rating of this problem acc to codeforces

I came up with another solution which I think is easier to understand (obvs im biased)

Call a "floor" a tower that can't be split horizontally. A floor of size n can be a 2xn block (1 way) or two 1xn blocks next to eachother such that the two blocks are never broken on the same layer. The second type of floor has n-1 layers. Each can be broken to the left, the right, or not broken at all ($$$3^{n-1}$$$) ways, which means the number of floors of size n is $$$f_n = 1 + 3^{n-1}$$$

All towers of size n are made of a tower size j, with a floor of size n-j on top. Thus, the number of towers size n is $$$\displaystyle t_n = \sum_{j=0}^{n-1} t_j f_{n-j}$$$. This takes $$$O(n^2)$$$ time to calculate, so we simplify:

where $$$p_n$$$ is a prefix sum

This was my code:

vector<ll> towers(maxN+1), psum(maxN+1);
towers[1] = 2;
psum[1] = 1;
for (int i = 2; i <= maxN; i++) {
	psum[i] = (psum[i-1] + towers[i-1]) % MOD;
	towers[i] = psum[i] + 3*(towers[i-1] - psum[i-1]) + towers[i-1];
	towers[i] = (towers[i] % MOD + MOD) % MOD;
}