0
$\begingroup$

The problem is proposed here and related to this question. 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.

Let $\sum_{i=0}^{k}x_i=S$. The straightforward method is enumerating $S$ from $0$ to $n-2k$, and using dynamic programming to count nonnegative solutions to $\begin{cases}&x_0 ⊕x_1⊕\cdots⊕x_k=0 \\&\sum_{i=0}^{k}x_i=S \end{cases}$ (this is the number of winning positions for the first player of a Nim with $k$ piles and a total of $S$ stones, allowing empty piles). But it runs in $O(n^3 k)$ which is too large.

I think there may be some other dynamic programming technique to solve it, but cannot work out that. Any thoughts are welcome.

$\endgroup$
  • $\begingroup$ Please make your question self-contained. $\endgroup$ – orlp Nov 24 '18 at 9:42
  • $\begingroup$ I've copied the description here. $\endgroup$ – Hang Wu Nov 24 '18 at 10:32
  • $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Nov 24 '18 at 11:20
0
$\begingroup$

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))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.