← 完整题目索引

PROJECT EULER · #0629

散石尼姆游戏

Scatterstone Nim

仅题目 · 待解原题 ↗

Alice 和 Bob 正在玩一种经过修改的 Nim 游戏,称为 Scatterstone Nim,Alice 先玩,与 Bob 轮流玩。游戏从任意一组石堆开始,石子总数等于 n

在玩家的回合中,他/她必须挑选一堆至少有 2 的石子并执行分割操作,将这堆石子分成任意一组 p 非空、任意大小的堆,其中 2pk 对于某个固定常数 k。例如,大小为 4 的一堆可以分为 {1,3}{2,2},或者 {1,1,2}(如果 k=3),另外如果 k=4,则分为 {1,1,1,1}

如果在给定回合中无法进行有效的移动,则另一位玩家赢得游戏。

获胜位置被定义为一组石堆,无论其他玩家做什么,玩家都可以最终确保胜利。

f(n,k) 为 Alice 在第一回合中获胜位置的数量,给定参数 nk。例如,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) 为所有 2kn 上的 f(n,k) 之和。例如,g(7)=66g(10)=291

g(200)mod(109+7)

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。