PROBLEM LINK:Author: Ankit Srivastava and Uttam Kanodia 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. $$ preXOR[0] = 0 \hspace{3 mm}\& \hspace{3 mm}preXOR[i] = A[0] \oplus A[1] \oplus \cdots \oplus A[i1]$$ $$ A[i] \oplus A[i+1] \oplus \cdots A[j] = preXOR[i1] \oplus preXOR[j]$$. Now, let me present an $O(N^2)$ solution for the problem.
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[i]] = k$ for all $i < l$.
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] \text{(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: 1) If size of the array $S$ is lesser than $\sqrt{N}$, then we can use brute force as given above. 2) 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: $$(x^{S[0]} + x^{S[1]} + \cdots + x^{S[L1]}) (x^{S[0]} + x^{S[1]} + \cdots + x^{S[L1]})$$ 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: $$(x^{S[0]} + x^{S[1]} + \cdots + x^{S[L1]}) (x^{NS[0]} + x^{NS[1]} + \cdots + x^{NS[L1]})$$ 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
This question is marked "community wiki".
asked 18 Jun '15, 15:19

I found an $O(N \sqrt N \log N)$ solution using FFT during contest, but I find hard to believe that it could run on 300000 numbers in 5 seconds. With that complexity, That's a problem even for simple algorithms, never mind FFT that has a horrible constant factor. We could use NTT, which is faster, but not that much faster (modulos vs complex numbers). answered 22 Jun '15, 00:16

Shouldn't it be
in the second code block? answered 26 Jun '15, 03:02

Both setter's and tester's solution aren't available. Have you in fact tried to solve it with threshold equal to sqrt(N)? I guess you should have very good implementation of FFT to make it pass. That FFT part works in NlogN, which is much more than running time of naive part (for sqrt(N) it will work in O(N))  therefore we are interested in picking higher threshold to make things better; I've checked several AC solutions, all of them use much higher constant  2000, 5000, 6000, 10000 and even 12000. answered 25 Jul '15, 03:01

Why do we need to handle $S$ differently for $S<\sqrt{N}$ and $S\geq\sqrt{N}$? I think for whatever $S$ we can just do FFT directly. The total running time would be $O(N\log{N})$. Am I missing sth? answered 22 Jun '15, 02:22
You can handle one group of identical xorprefixsums (at which starting and ending points can be) in O(N log N) using FFTs. The number of elements in that group doesn't matter very much.
(22 Jun '15, 02:46)
@yubowenok, for each S, check whether brute force will faster or FFT. and use the faster version.
(22 Jun '15, 11:28)
