Problem 806

Nim on Towers of Hanoi

This problem combines the game of Nim with the Towers of Hanoi. For a brief introduction to the rules of these games, please refer to Problem 301 and Problem 497, respectively.

The unique shortest solution to the Towers of Hanoi problem with $n$ disks and $3$ pegs requires $2^n-1$ moves. Number the positions in the solution from index $0$ (starting position, all disks on the first peg) to index $2^n-1$ (final position, all disks on the third peg).

Each of these $2^n$ positions can be considered as the starting configuration for a game of Nim, in which two players take turns to select a peg and remove any positive number of disks from it. The winner is the player who removes the last disk.

We define $f(n)$ to be the sum of the indices of those positions for which, when considered as a Nim game, the first player will lose (assuming an optimal strategy from both players).

For $n=4$, the indices of losing positions in the shortest solution are $3$,$6$,$9$ and $12$. So we have $f(4) = 30$.

You are given that $f(10) = 67518$.

Find $f(10^5)$. Give your answer modulo $1\ 000\ 000\ 007$.

汉诺塔取石子游戏

本题结合了“取石子游戏”和“汉诺塔”这两种游戏，其规则介绍请分别参见第301题和第497题。

对于包含$n$个盘子和$3$根柱子的标准汉诺塔问题，其唯一的最优解法共需$2^n-1$步。将该解法中出现的所有状态分别编号，初始状态（所有盘子都在第一根柱子上）编号为$0$，最终状态（所有盘子都在第三根柱子上）编号为$2^n-1$。

这$2^n$种状态中的每一种都可以视为取石子游戏的一个初始布局。由此布局开始，两名玩家轮流选择一根柱子，并从中移走任意数量为正的盘子。移走最后一个盘子的玩家获胜。

考虑所有作为取石子游戏初始布局时先手玩家必败的状态（假设两名玩家均采用最优策略），记$f(n)$为这些状态的编号之和。

对于$n=4$，所有必败初始状态的编号为$3$、$6$、$9$和$12$，因此$f(4) = 30$。

已知$f(10) = 67518$。

求$f(10^5)$，并将你的答案对$1\ 000\ 000\ 007$取余。