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🙂

1 Like

Thanks a lot❤️