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;
}

We're building the tower level by level (row by row, from bottom to top). At each level of height 1, we have two types of configurations:

1. LINKED (linked = 1): One horizontal 2×1 block spanning both columns

2. UNLINKED (linked = 0): Two separate 1×1 blocks side by side

The DP State dp[levels][linked] = "Number of ways to fill the remaining levels levels, starting with the given configuration (linked or unlinked)"

The Transitions When current level is LINKED:

If we have a horizontal block at this level, the next level can be:

• 2 different linked configurations (coefficient: 2)

• 1 unlinked configuration (coefficient: 1)

Formula: dp[levels][1] = 2 × dp[levels-1][1] + 1 × dp[levels-1][0]

When current level is UNLINKED:

If we have two separate blocks at this level, the next level can be:

• 4 different unlinked configurations (coefficient: 4)

• 1 linked configuration (coefficient: 1)

Formula: dp[levels][0] = 4 × dp[levels-1][0] + 1 × dp[levels-1][1]

Why These Numbers (2 and 4)?

The coefficients represent different ways blocks can be placed on top of the previous configuration while considering:

How blocks align with what's below Different heights and positions of vertical blocks that result in distinct final configurations

Base Case dp[0][0] = dp[0][1] = 1 When 0 levels remain, there's exactly 1 way (we're done).

Precompute: Calculate dp table for all possible n values (0 to 10^6)

Answer queries: For height n, the answer is dp[n-1][0] + dp[n-1][1]

Credit: https://www.youtube.com/watch?v=pMEYMYTX-r0

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;
const int MAXN = 1000001;

long long dp[MAXN][2];

void precompute() {
    // Base case: 0 levels remaining
    dp[0][0] = dp[0][1] = 1;
    
    // Compute for all possible levels
    for (int levels = 1; levels < MAXN; levels++) {
        // linked = 1: can place 2 linked or 1 unlinked configuration
        dp[levels][1] = (2LL * dp[levels - 1][1] % MOD + dp[levels - 1][0]) % MOD;
        
        // linked = 0: can place 4 unlinked or 1 linked configuration
        dp[levels][0] = (4LL * dp[levels - 1][0] % MOD + dp[levels - 1][1]) % MOD;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    precompute();
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        // Answer for height n is dp[n-1][1] + dp[n-1][0]
        // This represents starting from level 1 and filling (n-1) more levels
        long long ans = (dp[n - 1][1] + dp[n - 1][0]) % MOD;
        cout << ans << '\n';
    }
    
    return 0;
}