0
$\begingroup$

Given $n$ and $k$, I would like to know how to compute$$\sum_{\substack{x_0 ⊕x_1⊕\cdots⊕x_k=0\\x_i≥0,\ 0≤i≤k\\\sum\limits_{i=0}^kx_i≤n-2k}}\binom{n-k-\sum\limits_{i=0}^kx_i}k$$ in $O(nk·\log n)$ time, where $⊕$ is exclusive or.

$\endgroup$
2
  • $\begingroup$ This looks easy $\endgroup$
    – David P
    Nov 24, 2018 at 6:50
  • $\begingroup$ Could you please explain a little more? $\endgroup$
    – Hang Wu
    Nov 24, 2018 at 9:15

1 Answer 1

0
$\begingroup$

I finally figure out an answer. This paper "Nim Fractals" by Tanya Khovanova and Joshua Xiong gives a recursive 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))$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .