### izlyforever's blog

By izlyforever, history, 6 weeks ago,

nihal2001 posted a blog for asking the following question:

There are $n$ stones, two players take turn to choose $x$ stones, such that $1 \leq x \leq n$ and $x \And n = 0$. The one who cannot make choose lose.

Determine who is the winner, The first one or the second?

I proved that If $n$ belongs to https://oeis.org/A295897, the second player win(can be solved in $O(\log n)$).

My Question(Multiple piles version of above question):

There are $n_1, \cdots, n_m$ stones, two players take turn to choose an index $i$ and $x_i$ stones, such that $1 \leq i \leq m$, $1 \leq x_i \leq n_i$ and $x_i \And n_i = 0$. The one who cannot make choose lose.

Who will be the winner?

This turn out to compute Sprague-Grundy function for $n_1 \cdots, n_m$. The first player win if and only if $sg(n_1) \wedge \cdots \wedge sg(n_m) \neq 0$

I know how to compute $sg(n)$ in $O(n^2 \log n)$, but I can't give it a formula or compute efficiently like $O(\log n)$ or $O(\log^2 n)$

UPD: $O(n^{log_2 3} \log n)$ implement based on wery0's comment.

UPD2: $O(n^{log_2 3})$ implement based on wery0's talk.

• +31

 » 6 weeks ago, # |   +4 This is really an interesting question.I don't want to let it fall on deaf ears, so I comment again(sorry).Looking forward to talented players to help me solve this problem.
 » 6 weeks ago, # |   0 $sg(n) = MEX(\{sg(n-x): 1 \leq x \leq n, \space x\&n=0\})$Let $F(n)$ = number of $x$, such that $1 \leq x \leq n, \space x\&n=0$.Since we can count $MEX$ of $N$ numbers in $O(N)$, we can calculate $sg(n)$ in $O(F(n))$.To find $sg(n)$ we also should calculate $sg$ for some numbers $\leq n$. Let's do it for all numbers $\leq n$. It will work in $\sum_{i=1}^{n} F(i)$. Turns out that $\sum_{i=1}^{n} F(i) = O(n^{log_2 3}) \approx O(n^{1.59})$.So, the complexity of this solution is $O(n^{log_2 3})$. Maybe it is possible to do faster, idk.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Thanks!The only thing I don't understand is how to judging all reasonable x in $O(F(n))$. I can only solve it in $O(n^{\log_2 3} \log n)$ after your explanation.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 if $m$ is complement of $n$, then $F(n)$ is just all the submasks of $m$ and you can loop over them with one for cycle like this:for(int i = m; i > 0; i = (i-1) & m)this works because $(i-1)\text{&}m$ is the biggest number less than $i$ that is submask of $m$.
•  » » » » 6 weeks ago, # ^ |   0 Yes, This is exactly in wery0's talk, and this trick is used my implement.
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by izlyforever (previous revision, new revision, compare).