Dynamic programming — ~\mathcal{O}(xn^2)~

A well-known result from game theory states that the winning player of a game of Nim is determined only by the bitwise XOR of the piles' sizes. The first player has a winning strategy if (and only if) this value is not zero.

Let ~P_i~ be the probability that a pile contains ~i~ objects. Define ~d_{m,x}~ as the probability that the bitwise XOR of ~m~ random sizes is equal to ~x~. The values of ~d~ can be expressed with the recurrence relation

$$\displaystyle d_{m,x} = \begin{cases}1 & \text{if }m=0 \land x=0 \\ 0 & \text{if }m=0 \land x \ne 0 \\ \sum_{i=0}^N d_{m-1,i} P_{i \oplus x} & \text{otherwise}\end{cases}$$

where ~N~ is the maximal possible value of the XOR (one less than the first power of ~2~ greater than the maximal pile size ~n~) and ~\oplus~ the bitwise XOR operator.

The probability that the second player wins is ~d_{n,0}~. Because the first player wins if the second does not, we can calculate the values of ~d~ in ~\mathcal{O}(xn^2)~ and output ~1-d_{n,0}~.

Matrix exponentiation — ~\mathcal{O}(x^3 \log n)~

Let ~D_i~ be the vector ~\begin{pmatrix}d_{i,0} & d_{i,1} & \dots & d_{i,N}\end{pmatrix}^T~. The transformation that produces ~D_{i+1}~ from ~D_i~ is linear, and can therefore be expressed as ~D_{i+1} = MD_i~, where ~M~ is a matrix given by ~M_{i,j} = P_{i \oplus j}~.

Since the matrix multiplication is associative, ~D_n = M^n D_0~ we can calculate ~M^n~ using ~\mathcal{O}(\log n)~ matrix multiplications, for a total complexity to calculate ~D_n~ (which contains the solution ~d_{n,0}~) of ~\mathcal{O}(x^3 \log n)~.

This problem can also be solved in:

• Vector exponentiation — ~\mathcal{O}(x^2 \log n)~
• Faster multiplication — ~\mathcal{O}(x \log x \log n)~
• Even faster multiplication — ~\mathcal{O}(x \log x + x \log n)~

But ~\mathcal{O}(x^3 \log n)~ is enough to get AC.