Count Relations - Submit | CodeChef
someone can post the editorial for this question
This problems are form 2010,no solution link available.
This is the explanation.
Part 1 closed form: (3^n+1)/2 - 2^n
Part 2 closed form: 2*4^(n-1) - 3^n + 2^(n-1) + 2^n - (3^n+1)/2
The answer (for both 1 and 2) is in the form of a * 4^n + b * 3^n + c * 2^n + d for some small constants a,b,c,d.
You can calculate 4^n%MOD, 3^n%MOD, 2^n%MOD in log(n) time using fast exponentiation for an overall complexity of O(log(n)).
I would recommend trying out newer problems only.
p.s. I love the movie Your Name🙂
Thanks a lot❤️