Help with CSES Counting Towers

[utkarsh1729]

Problem Link: CSES - Counting Towers

My Code:

#include <bits/stdc++.h>
using namespace std;
 
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
using lld = long double;
 
const int MOD = 1e9+7;
const int MAXN = 1e6+5;
const ll INF = 1e18;
 
int main() {
    FASTIO
    
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<vector<ll>> dp(n+1, vector<ll> (2));
        dp[n][0] = 3, dp[n][1] = 5;
        for(int i=n-1; i>=2; i--) {
            dp[i][0] = 2*dp[i+1][0]+dp[i+1][1];
            dp[i][0] %= MOD;
            dp[i][1] = dp[i+1][0]+4*dp[i+1][1];
            dp[i][1] %= MOD;
        }
        cout << (dp[2][0]+dp[2][1])%MOD << "\n";
    }
    
    return 0;
}

I have verified the above code on the sample test cases and even verified it on the 100 test cases (on which it fails by giving TLE). But I am still getting RE on the first two tests and TLE on the last two tests. I think it has to do with the huge values of n but then I can’t think of a way to get over this. Can anyone please help?

@akshitm16 @cubercoder

[suman_18733097]

Why calculate again and again when you can pre-compute. Say you’ll pre-compute answers for all values of n<=N where N is maximum value of n. Then for each test case, you would be answering the query in O(1).
Try this, it may help.

[suman_18733097]

I think I also figured out the reason for Run time error.

For n = 1, it is giving segmentation fault. Try resolving this.

[utkarsh1729]

Thanks @suman_18733097 for your time and efforts.