0%

Problem 560


Problem 560


Coprime Nim

Coprime Nim is just like ordinary normal play Nim, but the players may only remove a number of stones from a pile that is coprime with the current size of the pile. Two players remove stones in turn. The player who removes the last stone wins.

Let L(n,k) be the number of losing starting positions for the first player, assuming perfect play, when the game is played with k piles, each having between 1 and n-1 stones inclusively.

For example, L(5,2)=6 since the losing initial positions are (1,1), (2,2), (2,4), (3,3), (4,2) and (4,4).
You are also given L(10,5)=9964, L(10,10)=472400303, L(103,103) mod 1000000007=954021836.

Find L(107,107) mod 1000000007.


互质取石子游戏

互质取石子游戏和一般的取石子游戏基本相似,唯一的区别是玩家每次只能从一堆中移走和堆的大小互质数目的石子。两名玩家轮流移走石子,移走最后一枚石子的玩家获胜。

假定双方都采取最优策略,游戏开始时有k堆石子,每堆中有最少1枚最多n-1枚石子,记L(n,k)为所有先手玩家必败态的数目。

例如,L(5,2)=6,这些必败态分别是(1,1),(2,2),(2,4),(3,3),(4,2)和(4,4)。
已知L(10,5)=9964,L(10,10)=472400303,L(103,103) mod 1000000007=954021836。

求L(107,107) mod 1000000007。