Problem 629

Scatterstone Nim

Alice and Bob are playing a modified game of Nim called Scatterstone Nim, with Alice going first, alternating turns with Bob. The game begins with an arbitrary set of stone piles with a total number of stones equal to $n$ .

During a player’s turn, he/she must pick a pile having at least $2$ stones and perform a split operation, dividing the pile into an arbitrary set of $p$ non-empty, arbitrarily-sized piles where $2 \leq p \leq k$ for some fixed constant $k$ . For example, a pile of size $4$ can be split into $1, 3$ or $2, 2$ , or $1, 1, 2$ if $k = 3$ and in addition $1, 1, 1, 1$ if $k = 4$ .

If no valid move is possible on a given turn, then the other player wins the game.

A winning position is defined as a set of stone piles where a player can ultimately ensure victory no matter what the other player does.

Let $f (n, k)$ be the number of winning positions for Alice on her first turn, given parameters $n$ and $k$ . For example, $f (5, 2) = 3$ with winning positions $1, 1, 1, 2, 1, 4, 2, 3$ . In contrast, $f (5, 3) = 5$ with winning positions $1, 1, 1, 2, 1, 1, 3, 1, 4, 2, 3, 5$ .

Let $g (n)$ be the sum of $f (n, k)$ over all $2 \leq k \leq n$ . For example, $g (7) = 66$ and $g (10) = 291$ .

Find $g (200) \mod (10^{9} + 7)$ .

分堆取石子游戏

爱丽丝和鲍勃正在玩一个分堆取石子游戏，爱丽丝先行动，然后轮到鲍勃，如此交替。游戏开始时，将 $n$ 枚石子分成若干堆，每堆中的石子数目任意。

轮到任一玩家行动时，该玩家先选择一堆至少有 $2$ 枚石子，然后将其分成 $p$ 堆，每一堆的石子数任意，但不能为空堆，同时 $p$ 满足 $2 \leq p \leq k$ ， $k$ 为某个事先约定的常数。例如，一堆共 $4$ 枚石子，如果 $k = 3$ ，那么可以分成 $1, 3$ 或 $2, 2$ 或 $1, 1, 2$ ；如果 $k = 4$ ，那么还可以分成 $1, 1, 1, 1$ 。

如果轮到某一玩家时没有可行的行动，则对手获胜。

如果玩家在面对特定的石子分堆时，无论对手如何行动，总能保证自己获得最终的胜利，则称之为必胜态。

对于给定的 $n$ 和 $k$ ，记 $f (n, k)$ 为爱丽丝在初次行动时必胜态的数目。例如， $f (5, 2) = 3$ ，必胜态包括 $1, 1, 1, 2, 1, 4, 2, 3$ 。此外， $f (5, 3) = 5$ ，必胜态包括 $1, 1, 1, 2, 1, 1, 3, 1, 4, 2, 3, 5$ 。

记 $g (n)$ 为遍取 $2 \leq k \leq n$ 时所有 $f (n, k)$ 的和。例如， $g (7) = 66$ 而 $g (10) = 291$ 。

求 $g (200) \mod (10^{9} + 7)$ 。