PROBLEM LINK:
Author: Ankit Srivastava and Uttam Kanodia
Tester: Roman Rubanenko
Editorialist: Amit Pandey
DIFFICULTY:
Medium
PREREQUISITES:
Fast Fourier Transform.
PROBLEM:
Given an array of N integers. You have to find count of all subarrays of size m, such that if a Nim Game is played on the subarray, second player will win. Do it for all possible values of m, 1 \le m \le N.
EXPLANATION:
It can be claimed using Nim Game theory that second player will win the game if XOR of the selected subarray is 0. We can find XOR of any subarray in O(1) time by creating a prefix XOR array.
.
Now, let me present an O(N^2) solution for the problem.
answer[n] = 0;
for i in range(0,n):
for j in range(i+1,n):
if preXOR* == preXOR[j]: //subarray having size (ji) has XOR 0.
answer[ji]++;
Consider a number k. If it appears l times in the preXOR array, then there will be ^lC_2 subarrays in array A whose XOR is zero. We can create an array corresponding to indices of k in preXOR array, and call it S. It means preXOR[S*] = k for all i < l.
for i = 0 to l1:
for j= i+1 to l1:
ans[ji]++; // there is a subarray of size (ji) having XOR 0.
It can be explained further,Consider that preXOR array is [1,2,3,1,1,4,1], then the array S for k=1 will be [0,3,4,6] ext{(0 based indexing)}.
The above solution can take up to O(N^2) time in the worst case, as size of S can be O(N). To improve it, we can do the following modifications:

If size of the array S is lesser than \sqrt{N}, then we can use brute force as given above.

If size of the array S is greater than \sqrt{N}, then the above solution will take more time. So, we can use the FFT to optimize the solution to time Nlog(N).
Number of subarrays of size K having XOR 0, will be coefficient of x^K in following polynomial:
The powers of x in the above polynomial are negative as well, therefore we do a small modification in above polynomial to make all the powers positive. It will be equivalent to the coefficient of x^{N+K} in the following polynomial:
Which can be done in O(Nlog(N)) time using Fast Fourier transform. The FFT will give answer corresponding to all possible value of m altogether.
We can repeat the above procedure for each distinct element k of preXOR array. The total count of subarrays corresponding to each value of m will be the count of subarrays of size m for each distinct value of k.
Worst case complexity of the above procedure will be O(N \sqrt{N} \log{(N)}).
Problems to solve:
Solution:
Setter’s solution can be found here
Tester’s solution can be found here