OMG, Thank you!! The example you gave was clear in pointing out my error. Unfortunately I did look up other solutions before I made this post hoping I'd find someone else with a similar approach, so I understood the code that you posted :/ .Thanks for the detailed response on how to fix my approach too, much appreciated.

Here is the optimised solution:

I've actually ended up changing what b is. Now b(n) is the number of combinations for 2xn towers if we start with width-1 blocks. Also, k is the height of the remaining tower. Still, the main idea of the solution is the same.

Since a(n) = 1 << (n-1), we can see that:

a(n) = 1 << (n-1) = (1 << (n-2)) * (1 << 1) = a(n-1) * 2

Let's start with b. For each k, we have a(n-k) * a(n-k) combinations for the width-1 blocks and c(k) combinations for the rest of the tower, so sum(k = 0 to n-1) a(n-k) * a(n-k) * c(k) combinations in total.

b(n) = sum(k = 0 to n-1) a(n-k) * a(n-k) * c(k)
     = (sum(k = 0 to n-2) a(n-k) * a(n-k) * c(k)) + a(n-(n-1)) * a(n-(n-1)) * c(n-1)
     = (sum(k = 0 to n-2) a(n-k-1) * 2 * a(n-k-1) * 2 * c(k)) + a(1) * a(1) * c(n-1)
     = 4 * (sum(k = 0 to (n-1)-1) a(n-k-1) * a(n-k-1) * c(k)) + 1 * 1 * c(n-1)
     = 4*b(n-1) + c(n-1)

In c, after adding a 2x(n-k) block, we have b(k) + c(k) combinations for the rest of the tower, so sum(k = 0 to n-1) b(k) + c(k) combinations in total.

c(n) = sum(k = 0 to n-1) b(k) + c(k)
     = (sum(k = 0 to n-2) b(k) + c(k)) + b(n-1) + c(n-1)
     = c(n-1) + b(n-1) + c(n-1)
     = 2*c(n-1) + b(n-1)

These are correct as long as n-2 >= 0, so it won't work for n = 1. This will be our base case. There is only one way to split a 2x1 tower into width-1 blocks, and one way to split it into width-2 blocks, so b(1) = 1 and c(1) = 1.

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

#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
const ll MOD=1e9+7;

int main(){
    fastio;

    ll tc;
    cin>>tc;
    while(tc--){
        ll n;
        cin>>n;
        ll b[n+1]={1,1}, c[n+1]={1,1};
        for(ll i=2; i<=n; i++){
            b[i]=(4*b[i-1]+c[i-1])%MOD;
            c[i]=(2*c[i-1]+b[i-1])%MOD;
        }
        cout<<(b[n]+c[n])%MOD<<endl;
    }

    return 0;
}

Here's where it gets interesting: As you can see, this is basically the same as my previous solution. However, the idea is completely different.

The states in these two solutions are actually the same. In each solution, we work level by level with two cases. In the previous solution, the two cases are the previous level either being split or not split, and this solution the cases are the current level either being split or not split. Because of this, their only difference is that in the previous solution, the n for both the base case and the value we print are smaller than the ones in this solution by 1.

Thanks for the explanation. I had looked up others’ solutions before I made this post to check if anyone else made the same mistake as me but didn’t find any. Your diagram was clear and understandable don’t worry :)