0%

Problem 629


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\le p\le 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\le k\le n$. For example, $g(7)=66$ and $g(10)=291$.

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


分堆取石子游戏

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

轮到任一玩家行动时,该玩家先选择一堆至少有$2$枚石子,然后将其分成$p$堆,每一堆的石子数任意,但不能为空堆,同时$p$满足$2\le p\le 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\le k\le n$时所有$f(n,k)$的和。例如,$g(7)=66$而$g(10)=291$。

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