Now please don't go downvoting the blog as there already are blogs and editorials on this, I know, please read my question though
So, I solved this problem using a 2d dp — dp[n][2] which was the solution I found in almost all of the editorials and blogs. But here's something interesting my friend found,
dp[i] = 6*dp[i-1] - 7*dp[i-2]
Apparently this recursive relation also solves the problem...
So, does anybody have an intuition for this?
I found it here
I would also like to tag the person who wrote this code — Jonathan_Uy
Make all the configurations for n = 2, and see how you can extend it to n = 3. I'm able to get the given recurrence relation but since it involves lots of drawing its really hard to explain it here.
this is a explanation: write the recursive 2d in a matrix:
f:[4 1] s:[1 2]
~~~~~~~~
vector chotiGand, badiGand; chotiGand.emplace_back(1); badiGand.emplace_back(1); chotiGand.emplace_back(5); badiGand.emplace_back(3); for(int i=2 ; i<=1e6 ; i++){ int choti = ((chotiGand[i-1]*4)%mod + (badiGand[i-1]*1)%mod)%mod; int badi = ((chotiGand[i-1]*1)%mod + (badiGand[i-1]*2)%mod)%mod; chotiGand.emplace_back(choti); badiGand.emplace_back(badi); } int t; cin>>t; while(t--){ int n; cin>>n; cout<< (chotiGand[n-1]+badiGand[n-1])%mod<<endl; } ~~~~~~ Almost similar approach by which i have solved, maybe you can understand by taking a small base case of 1 and 2 to visualize the whole tower of n size.
The main catch in this approach is that how the top layer is looking and how we can proceed to upper level
I think i can better explain by writing on page by drawing it.....