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
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