Блог пользователя alt_1234AA

Автор alt_1234AA, история, 2 года назад, По-английски

Good Evening/Afternoon/Morning everyone ( Basically, Salaam Dosto )

I am able to solve only subtask 1 of Max Shift After XOR. I am not able to understand the editorial given out there.

I asked in announcement on codeforces page about hints and approaches but no one replied. So I am writing a blog for help. Any please explain your approach and if you understood the problem please explain that too.

Thank you in Advance and sorry for my poor English.

And Have a nice day

Problem Link : link

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Consider what happens to the prefix xor array of $$$a$$$ when you do a circular right shift on $$$a$$$. The last element of prefix array gets popped, $$$a[n-1]$$$ gets added to the start of prefix array and every other element of prefix array gets XOR'd by $$$a[n-1]$$$. Now you need the number of distinct elements in this array. Since XORing by a number provides a one-to-one mapping, we can XOR any set of values by $$$x$$$ and the mapping will be preserved(and hence the number of distinct elements will remain same). So instead of XORing the entire prefix array by $$$a[n-1]$$$, we will insert the already XOR'd value to the beginning and keep track of what we have XOR'd till now.

https://www.codechef.com/viewsolution/67263230