Project Euler #400 Fibonacci tree game

2019-03-06

 


Project Euler #400:

斐波那契树是一棵递归定义的二叉树:

  • \(T(0)\)是一棵空树。
  • \(T(1)\)是只有一个结点的二叉树。
  • \(T(k)\)有一个根结点,其左右子树分别为\(T(k-1)\)和\(T(k-2)\)。

在这棵树上,两个玩家进行一个取结点游戏。每一回合,一名玩家选择一个结点,并取走以这个结点为根结点的子树。
取走整棵树的根结点的玩家将输掉这个游戏。

以下是当\(k=1 \sim6\)时,先手玩家面对\(T(k)\)第一步所有的必胜走法:

记\(f(k)\)是先手玩家面对\(T(k)\)时第一步所有的必胜走法数目(所谓必胜走法指保证后手玩家没有必胜策略)。

例如,\(f(5) = 1\)以及\(f(10) = 17\)。

求\(f(10000)\)。给出其最后18位数作为你答案。


算是PE上的第一道题吧,特意选了一个看起来比较友善水的。

做这题之前不会树上删边游戏,就对着题目看了一下午啥也看不出来,问了starria之后才知道还有这么个模型。

我好菜啊。

关于树上删边游戏,我就不多说了,在这里放个链接:

树上删边游戏及其拓展(公平博弈:克朗原理+费森原理)

学会了之后就很简单了,这个题就是要求删掉一条边使得SG值为0的方案数。

令\(F[i]\)表示\(T(i)\)的SG值,\(A[i][j]\)表示\(T(i)\)在删掉一条边后SG值为\(j\)的方案数,经过打表可以发现\(j\)的最大值为139301。

由于Fibonacci Tree的特殊构造,我们可以得到转移式:

\(F[i]=(F[i-1]+1) \oplus(F[i-2]+1)\)

\(A[i][(j+1) \oplus(F[i-1]+1)]+=A[i-2][j]\)

\(A[i][(j+1) \oplus(F[i-2]+1)]+=A[i-1][j]\)

需要注意的是:如果删掉的边与根节点相连,需要另行讨论。

 

Leave a Reply:

电子邮件地址不会被公开。 必填项已用*标注