An abacus has several horizontal rods. rods[r] lists the positions of the beads on rod r (distinct non-negative integers, in any order); position 0 is the left end of the rod, and a rod can be arbitrarily long to the right.
Two players alternate turns. On a turn, a player picks one bead on one rod and slides it left by at least one position. A bead cannot move below position 0, and it cannot land on or jump over another bead of the same rod. Beads never change rods. A player who cannot move on their turn loses.
A move is a pair (bead, destination position). Assuming both players play perfectly, return the number of different first moves that guarantee a win for the player who moves first. Return 0 if the first player loses whatever they do.
Examples
Input: rods = [[7, 9, 10], [5, 6, 11]]
Output: 3
Input: rods = [[4, 8, 5], [], [2, 0, 1]]
Output: 1
Explanation: the rod [2, 0, 1] is stuck. On the first rod, the only winning move slides the bead at 4 to position 2.
Constraints
1 <= len(rods) <= 1000, and the rods hold at most2 * 10**5beads in total0 <= position <= 10**18; positions on one rod are distinct- Searching the game tree is hopeless: positions are huge.
Goals
- Recast a token-sliding game as a game on the gaps between tokens
- Find which gaps matter to the outcome and which moves can be undone
- Count every winning first move, including the ones that change a gap that does not matter