Problem solving using Binary Exponentiation

Binary exponentiation (also known as exponentiation by squaring) is a trick which allows to calculate an using only O(logn)multiplications (instead of O(n) multiplications required by the naive approach).

So here we will be using this concept to solve two problems:

Problem 1: Big Mod (Online Judge)
This question is very straight forward in which you just need to apply the binary exponentiation algorithm to solve it in O(log n) time complexity. Here is the solution for your reference.


This problem is based on combinatorics, to solve this problem consider that there are 4 different colors namely (R, G, B, Y) and you need to form a string of length 2n-2 where n is an integer in which there should be a substring of length exactly n of the same color.

After this, you will derive a general formula for n>=4 where n=3 will be your special case. Below is the solution for your reference.


Thank You
If you find any error or you have some different ideas to solve the problem then do comment.

Comments