Problem 344

Silver dollar game

One variant of N.G. de Bruijn’s silver dollar game can be described as follows:

On a strip of squares a number of coins are placed, at most one coin per square. Only one coin, called the silver dollar, has any value. Two players take turns making moves. At each turn a player must make either a regular or a special move.

A regular move consists of selecting one coin and moving it one or more squares to the left. The coin cannot move out of the strip or jump on or over another coin.

Alternatively, the player can choose to make the special move of pocketing the leftmost coin rather than making a regular move. If no regular moves are possible, the player is forced to pocket the leftmost coin.

The winner is the player who pockets the silver dollar.

A winning configuration is an arrangement of coins on the strip where the first player can force a win no matter what the second player does.

Let W(n,c) be the number of winning configurations for a strip of n squares, c worthless coins and one silver dollar.

You are given that W(10,2) = 324 and W(100,10) = 1514704946113500.

Find W(1 000 000, 100) modulo the semiprime 1000 036 000 099 (= 1 000 003 · 1 000 033).

银币游戏

N.G.德布鲁因的银币游戏的其中一个变种如下所述：

在一长条的方格上放置有一些硬币，最多每个方格一枚硬币。只有一枚称为银币的硬币是有价值的。两名玩家轮流进行操作，每一轮玩家可以选择进行一次常规操作或者进行一次特殊操作。

常规操作就是选择一枚硬币，并将其向左移动一格或多格。硬币不能移出方格，也不能跳过或重叠其它硬币。

除了常规操作，玩家也可以选择进行特殊操作，将最左边的硬币放进自己的口袋。如果不存在可以进行的常规操作，玩家必须将最左边的硬币放进自己的口袋。

将银币装进自己口袋的玩家获胜。

所谓必胜态指的是无论后手玩家如何操作，先手玩家都必然获胜的硬币放置状态。

记W(n,c)为一长条有n个方格，放置有c枚无价值硬币和一枚银币时的必胜状态数目。

已知W(10,2) = 324以及W(100,10) = 1514704946113500。

求W(1 000 000, 100)，并模半素数1000 036 000 099 (= 1 000 003 · 1 000 033)取余。