@meooow I was trying something very similar. Even though your solution is obviously correct, I’m struggling to understand it completely. I understand the part that it has periodicity on powers of 2 that are >= chain length. I also understand that it’s convenient to add 0’s to the end to make it power of two, since it seems to be easier to explore what happens on powers of two. I’m not getting the part where you merge 2 halves. Can you please elaborate more?
I have updated my answer to explain the recursive part in greater detail, take a look 
Wow… that is some solution
I have taken the following approach in solving:
Noticed that for any delta, the result is the XOR of the value of the result at “delta = 1” with the XOR of all elements present at depth delta, ie
RESULT for delta(D) = Result for delta(1) ^ (Result of XOR of all elements present at depth D).
lets say for the example given in question itself,
Result of delta(1) = 1^5^8^7 = 11
Now for the queries,
Result of delta(2) = 11 ^ (Result of XOR of all elements present at depth 2)
= 11 ^ (5^7)
= 9
Result of delta(3) = 11 ^ (Result of XOR of all elements present at depth 3)
= 11 ^ (8)
= 3
After this the pattern just repeats with the fact that delta(0) = value present in array initially ie 1.
Can someone please point out what is wrong with this approach and where do I need to correct, the editorials and comment by all the people here are really good but just need to know how can it be solved if I take this approach and if it can be solved using this or not.Link to my solution is https://www.codechef.com/viewsolution/15395688
Hey everybody
I’ve made a video in 2 parts for this problem.
Part 1: https://youtu.be/FhC6A4mvXUw(Weasel does XOR on Tree - Part 1)
Part 2: https://youtu.be/HIVZ9HVSIb0(Weasel does XOR on Tree - Part 2)
Did you guys notice the amazing look alike of “Sierpinski Triangle” Fractal in this problem? See the part 2 especially as I have discussed about it there.
Hey everybody
I’ve made a video in 2 parts for this problem.
Part 1: https://youtu.be/FhC6A4mvXUw (Weasel does XOR on Tree - Part 1)
Part 2: https://youtu.be/HIVZ9HVSIb0 (Weasel does XOR on Tree - Part 2)
Did you guys notice the amazing look alike of “Sierpinski Triangle” Fractal in this problem? See the part 2 especially as I have discussed about it there.
1 Like
It may be a brute-force approach but I am really curious where my
[1] is going wrong, apart from it's complexity. I used adjancy matrix to represent the tree and simply XOR'ed the values present in the sub-trees for every node.
[1]: https://www.codechef.com/viewsolution/15370042Yes 
The binomial coefficients modulo 2 is exactly the Sierpinski Triangle. The author used this term when describing his solution, however I didn’t.
Math is love <3
Sierpinski triangle is T[height][time - 1] = T[height - 1][time - 1] xor T[height][time - 2] = ( height & (time - 1) == 0), then you can use SOSDP in the mask height for all mask ~(time - 1)
in Boolean Algebra part: https://www.zeuscat.com/andrew/chaos/sierpinski.html
2 Likes
how is f(/,u) the number of sequence (v0,v1,…v/) ?? i cant understand…
I used a considerably different approach for this problem, similar to some of the comments. First I realised that whether an element(in chain instead of tree) is present in the answer or not depends solely on k and d(depth) of that element. Let n be the maximum depth of the chain. Then i observed that if all set(1) bits in d are 0 in k(or 1 in binary negation of k), the element is present in xor(answer), else absent. Let x denote the next power of 2 >=n. I then used self explanatory approach to calculate answer for negation of all possible k less than x in O(nlogn). Also, please confirm that this works for all corner cases.
Heres the link to my solution, Please upvote. AC in 0.15 seconds
https://www.codechef.com/viewsolution/15387157
Tried to make a video editorial I’m really bad at this but please do tell me if it’s helpful