I am studying game theory and I am wondering how many winning combinations are possible for Nim game? Suppose, stones = 500 and piles = 5. With these number, there are many initial game positions are possible. like [1, 2, 4, 3, 490], [100, 100, 100, 100, 100], [100, 200, 100, 100], [0, 200, 200, 50, 50] and so on. So basically there are
stones^piles combinations possible. Among these, some will yield
Xor > 0 and considered as winning possible.
My question is - how many winning initial positions are possible for given
piles? Instead of checking all possible combinations(which is impossible for larger inputs), is there any smart way to solve this?
This is not a homework or programming contest problem.