Sum of zero nim sum series
I finally figure out an answer. This paper "Nim Fractals" by Tanya Khovanova and Joshua Xiong gives a formula to count the solutions to $$\begin{cases} x_0 \oplus \cdots \oplus x_k =0 \\\sum_{i=0}^{k}x_i=S\end{cases}$$ in $O(kS)$. Denote the number as $f(k,S)$. We may utilize $f$ to see that the problem reduces to $\sum_{S=0}^{n-2k}\binom{n-k-S}{k}f(k,S)$. The overall complexity is $O(nk\cdot log(n))$.