ishat_jha's blog

Chef and Riffles — Question Help
By ishat_jha, history, 11 months ago, In English

Hello Codeforces Community, I recently started reading CP-Algorithms site. While doing the practice of binary exponentiation questions, I am stuck at the question:- Chef and Riffles Link:- https://www.codechef.com/JAN221B/problems/RIFFLES

Any help regarding the code explanation, approach would be very helpful.

Thanks!!

Ishat Kumar Jha

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the point here is to remember that we are applying some operation of permutation to the sequence, and we are doing it again and again, so in a sense it's similar to say, adding 2 numbers again and again, or like that,

So we are inherently saying that since we have to apply permutation again and again over the sequence, why not just apply the permutation operation on the permuation thing n times and then do the operation on the original seq at hand when the bit in the power is 1, meaning it had to be done at that time, like say the case of pow(a,b), so doing a*a*a*a*... b times, say b = 4, in binary = 100 so you have to do a*a*a*a, you have to calculate it and reach there, and when you are that set bit of 1, that means you've reached a*a*a*a, but you got there also right, by multiplying a with previous a's, and only when you had to strike the iron hot you did,

I don't know i was able to explain it well, but i hope it helps

→ Reply