We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
M = 109+7.
To calculate (ab)%M and we know b can be very large(3N) .
Using Fermat's little theorem (a(M-1))%M = 1, first we will do b=b%(M-1) and then calculate (ab)%M by using fast exponentiation.
References :-
1. Codechef Discussion
2. Geeksforgeeks
Tower 3-coloring
You are viewing a single comment's thread. Return to all comments →
Hint:-
Here total number of possibilities are 3(3N).
M = 109+7.
To calculate (ab)%M and we know b can be very large(3N) .
Using Fermat's little theorem (a(M-1))%M = 1, first we will do b=b%(M-1) and then calculate (ab)%M by using fast exponentiation.
References :-
1. Codechef Discussion
2. Geeksforgeeks
sorry bro,i cannot understand how it is 3 to the power 3 to the power N. can u explain me?
Hi,
For user input n, there would be 3^n blocks. Each of these 3^n blocks can be coloured in 3 ways.
You can color1 block in 3 ways, You can color 2 blocks in 3*3 (3^2) ways.. .. You can color 3^n blocks in 3^(3^n)) ways.
thanks alot......